引言
可持续化线段树(又叫主席树、函数式线段树),顾名思义就是保存线段树的所有历史版本,并且利用他们共同的数据来减少时间和空间的消耗
相比普通的线段树维护当前节点对应的区间的信息,可持续化线段树能够记录每次修改后的线段树,可以解决区间第k个数大小的问题。
主席树能够保存线段树的所有历史版本,这肯定不会是每一个线段树都存储下来(这样一定会MLE的),而是在每次修改的时候只记录修改的结点,没有修改的结点还用原来的线段树里面的结点,这样在线段树中修改某一个值得时候,只需要新增logn个结点来记录这修改了的logn个结点,其他的结点都是不变的,充分利用其中的共有数据。主席树中的每一个结点保存的是一个线段树,维护的区间相同, 结构相同,只有保存的信息不同,这样主席树中的结点就具备了加减性。
实现
建树
原始的树可以看成是一课空树tree[0],树中的任何结点的左右结点都是这个空结点,载入原始数据的过程可以看成是第一个历史版本,其他的过程和普通的线段树相同,临界判断,向下更新。
更新
在原来的线段树上进行更改,所修改的每一个结点都是充分分配空间的新结点,同时将父节点指向当前的结点,再用root数组存储当前线段树的根节点。这里很巧妙地用到了引用操作(&),例如update(tree[id].l,l,r,v),同时update函数的变量表为update(int &id,int l,int r,int v),函数体的开头就是tree[++cnt]=tree[id];id=cnt; 这样巧妙地操作顺便将父节点的左右孩子结点指针也指向了该结点,这样就跟普通的线段树相差无几了
查询
查询的操作基本上跟普通的线段树一样,就是我们可以随便在哪一个历史版本中查询,比如query(root[k],l,r) 表示在第k个历史版本中查询
POJ 2104 区间第k大问题
题意
给出n个数,查询区间[l,r]中第k大的数是多少
题解
- 首先数据范围比较大,考虑进行离散化,即对所给的数列进行排序,利用每个数在排序后的数组中的下标进行处理
- 使用可持续化线段树,建立n个线段树,从第一个线段树开始,后面每一个线段树多一个数的信息
- 实现查询,因为所建立的这n个线段树维护的区间相同,结构相同,将查询区间两个端点的线段树相减就可以得到[l,r]中的信息,再使用二分法递归找到查询的数在整个数组中的排位
代码
1 |
|
HDU 4348 区间增加+可持续化
题意
给出一个序列,并为每次插入操作添加时间点,进行一下操作:查询区间[l,r]的和;查询时间点k下的[l,r]区间和;更改时间点;为区间[l,r]添加数
题解
- 为每一个历史版本创建一颗线段树,同时充分利用共有数据,只增加有改变的结点
- root数组记录每一个历史版本线段树的根节点信息
- lazy思想,在查询的时候再进行向下的更改
代码
1 |
|