可持久化线段树学习笔记
起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭
可持久化线段树的本质是很多棵形态完全相同的线段树。
也可以理解成是，保存了不同时刻版本的线段树的数据结构。
如果没有可持久化线段树，那么我们如果需要不同时刻的线段树，无脑的做法可能是，需要多少个时刻的线段树，就建多少棵线段树。
但是空间绝对gg，我们考虑每次修改，其实对于一次修改，线段树上只有很少一部分被修改了，其他部分都一样。
因此，我们很容易想到，我们何不只考虑修改的部分，其他部分共用，以减少时间和空间消耗呢？
* 可持久化线段树是利用函数式编程的思想，对记录的数据只赋值不修改，每次插入一个数据后保存一个历史版本，然后利用线段树的结构完全相同，可以直接相减的特性进行区间询问。
可持久化线段树有几个经典应用，比如求区间第k大 静态区间第k大 动态区间第k大
静态区间第k大的思想：
* 首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.
* 然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.
* 如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的**差线段树**上作二分,就可以求得区间第k大值.
* 差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.
* 现在,可持久化线段树出现为你解决最后一个问题,空间问题.内存很小,不能够存下n颗线段树,但是,第2条中提到,由于第i颗线段是是第i-1颗线段是插入仅一个值得到的,两颗线段树的区别不大,仅有log(n)个节点发生了改变,我们仅仅需要记录这log(n)的数据就可以记录这个增量,这就是可持久化线段树.
以及求区间中不同数的个数 spoj-dquery 求区间中不同数的个数
思想其实和离线线段树是一样的。
在学习可持久化线段树的时候，遇到过一个叫"权值线段树"的概念
其实并不是什么新东西，只不过是把值作为节点来考虑，参考逆序对的线段树|树状数组 求法...（由于是在值域上建立线段树，所以常常需要离散化）
这思想不是很常见么....感觉完全没必要安个名字...以及，怎么不给BIT也起个叫权值BIT啊orz
参考资料：