普通线段树
普通线段树就是一种能储存一个区间信息的一种二叉树，其每个节点都可以都可以储存一段区间的总体信息（例如和、最值等）。利用这些特性可以很方便地求出某一段区间的和、最值，在这里就不加讨论了。
可持久化线段树
可持久化线段树，又称主席树，是可以持久的一种数据结构。
构建
可持久化就是指可以很快地访问某一个历史时刻的信息，不需要再重新构建、还原。
如下图所示，是一棵普通线段树。节点内的值为节点编号，其旁边的值为它的数据（总和）。
假设我们心血来潮要把第 4 个节点修改为 3，直接修改？这显然是不科学的，因为这样会破坏历史版本，违背了可持久化的原则。
既然不能修改，我们就在 4 的旁边新建一个节点（编号为 8），其值为 3。
然后我们就要把它的父亲更新一下，既然又不能直接修改，我们继续新建一个节点！并且把这个节点的 left 指向新节点 8，right 指向没有发生变化的节点 5。
以此类推，我们一直这样更新到根节点，我们就得出了这么一个图：
这时我们惊奇地发现，这个图居然有两棵线段树。其中以 1 为根的就是旧的线段树，以 10 为根的就是修改后的线段树。这时无论我们要查询哪个历史版本，都只需要从对应的根节点查询即可。
概述
如果要快速地查找历史版本，一个比较朴素的办法就是直接保存所有版本，在用到的时候直接查询。但是这样做的空间复杂度非常感人，为 $O(n^2)$，令我们停下了幻想的脚步。
但是我们发现，相邻的两个版本的线段树，只修改了 1 个数据，对于线段树来说就意味着修改了 $\log{n}$ 个节点。这样的话，就有很多无需修改的节点，没有必要再复制一份。
所以可持久化线段树就把那些节点重复利用，只新建有更改的点，这样的话每次修改只会新建 $\log{n}$ 个节点，空间复杂度从 $O(n^2)$ 降低到 $O(n \log{n})$。而时间复杂度也无变化。
代码
如果要实现可持久化线段树，那么内存池（动态开点）是必不可少的。
struct NODE { int lc, rc; } node[MAXN * 20];
int pool=2;
int inline AllocNode(const int old) {
node[pool] = node[old]; // 继承于旧节点
return pool ++;
}
node[1] = (NODE){ 1, 1 }; // 空节点
然后就要实现修改一个点，我们就像普通线段树那样从上往下查找，往上合并时就新建节点来维护就可以了。
int edit(const int root, const int pos, const int val, const int l, const int r) {
int cur = AllocNode(root);
if (l == r) {
/* Your code here */
return cur;
}
int mid = (l + r) >> 1;
if (pos <= mid) node[cur].lc = edit(node[cur].lc, pos, val, l , mid);
else node[cur].rc = edit(node[cur].rc, pos, val, mid+1, r );
Maintain(cur);
return cur; // 返回新版本的根节点
}
然后的话，查询某个版本，就从对应版本的根节点开始，像普通线段树一样查找即可。
int query(const int root, const int s, const int t, const int l, const int r) {
if (s <= l && r <= t) return node[root].sum;
if (r < s || l > t) return 0;
int mid = (l + r) >> 1;
return query(node[root].lc, s, t, l, mid) + query(node[root].rc, s, t, mid+1, r);
}
例题
区间第 k 大问题
区间第 k 大问题可以说是可持久化线段树的 A+B problem，虽然它也可以用其它方法来做。
题意
区间第 k 大问题就是给你一个区间，有多个询问（在线），让你求出指定区间 [l, r] 的第 k 大的值。
思路
对于这个问题，我们可以先二分一个值 mid，定义答案的范围是 (l, r]，查询在 [l, r] 中比 mid 要小的值的数cnt，如果 cnt < k，那么 mid的值肯定过小，所以我们要往右半部分二分。
这样的话，我们的问题就变成了如何求 [l, r] 中比 mid 要小的数的数量。
这个问题有点特殊，我们先考虑一个求 [1, n] 中比 mid 要小的数的数量的问题。这个问题显然要离散化，然后构建一棵权值线段树，求比 mid 小的数量，我们就只需要在这棵线段树中查询 [1, mid-1] 区间的和即可。
如果换成区间 [l, r]，因为是权值线段树，所以我们可以把这个问题分解为 [1, r] - [1, l-1]，这样的话，我们就需要一个历史版本为 r 和 l-1 的历史版本，我们就把这 n 个数从左往右插入，新建 n 个版本的主席树即可。
时间复杂度为 $O(m \log^2{n})$，其中 m 为询问个数；空间复杂度为 $O(n \log{n})$。这就是可持久化线段树的典型例题。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：可持久化线段树”