本系列文章将于2021年整理出版。前驱教材：《算法竞赛入门到进阶》 清华大学出版社
网购：京东 当当 作者签名书：点我
有建议请加QQ 群：567554289
文章目录
- 1. “区间第k大”问题
- 2. 区间内小于等于k的数字有多少
- 3. 区间内有多少不同的数字
- 4. 区间更新
- 习题
前言：
可持久化线段树（Persistent segment tree），或称为函数式线段树。中文网上把类似的算法思路称为“主席树”，“主席”并没有确实的含义，而是诙谐的说法。NOIP选手黄嘉泰说：“这种求 k k k大的方法（函数式线段树）应该是我最早开始用的”（https://www.zhihu.com/question/31133885/answer/52670974）。黄嘉泰的拼音缩写HJT，正好是古月(H)金帛(J)氵寿(T)的缩写，所以被网民们称为“主席”树。
函数式编程（Functional programming），与面向对象编程（Object-oriented programming）、过程式编程（Procedural programming）并列。
以下是正文。
可持久化线段树 是基本线段树的一个简单扩展，是使用函数式编程思想的线段树，它的特点是支持询问历史版本，并且利用历史版本之间的共用数据来减少时间和空间消耗。
可以用动画做比喻来解释它的思想：
（1）一秒动画由20帧左右的静态画面连续播放而成，每2个相邻画面之间差别很小；
（2）如果用计算机来制作动画，为节省空间，让每一帧画面只记录与前一帧的不同处；
（3）如何生成完整的每一帧画面？从第1帧画面开始播放，后面的每一帧用自己的不同处替换前一帧的相同位置，并填补上相同的画面，就生成了新的画面。
（4）两帧不同时间的画面做“减法”，得到一个新的画面，这个新画面反映了两个时间点之间的信息。
与动画类似，可持久化线段树的基本思路是：
（1）有多棵线段树（每棵线段树是一帧画面）；
（2）相邻两棵线段树之间差别很小，所以每棵线段树在物理上只需要存储与前一棵的不同处，使用的时候再填补并生成一棵完整的线段树；
（3）任意两棵线段树能“相减”得到一棵新线段树，它往往包含了题目需要的解。
可持久化线段树的基本特点是“多棵线段树”，根据具体情况，每棵线段树可以表示不同的含义。例如在“区间第 k k k大问题”中，第 i i i棵树是区间 [ 1 , i ] [1, i] [1,i]的线段树；在“hdu 4348区间更新问题”中，第 i i i棵树是第 t t t时间的状态。
需要建多少棵树？题目给定包含为 n n n个元素的序列，每次用一个新元素建一棵线段树，共n棵线段树。
每棵树有多少结点？线段树的叶子结点记录（或者代表）了元素，如果元素没有重复，叶子节点就设为 n n n个；如果元素有重复，根据情况，叶子结点可以设为 n n n个（例题hdu 5919），也可以设为不重复元素的数量（例题洛谷P3834）。
可持久化线段树用到的技术包括：前缀和思想 + 共用点 + 离散化 + 权值线段树（可以相减） + 动态开点。
下面用经典问题“区间第 k k k大”来介绍可持久化线段树的思想，并给出模板，然后介绍几个典型例题。
1. “区间第k大”问题
主席树 洛谷 P3834
题目描述：给定n个整数构成的序列a，队指定的闭区间[L, R]，查询区间内的第k小值。
输入：第一行包含2个整数，分别表示序列长度n喝查询个数m。第二行包含n个整数，第i个整数表示序列的第i个元素ai。下面有m行，每行包含3个整数L，R，k，表示查询区间[L, R]内的第k小值。
输出：对每个询问，输出一行一个整数表示答案。
数据规模：1 ≤ n, m ≤ 2* 1 0 5 10^5 105, |ai| ≤ 1 0 9 10^9 109, 1 ≤ L ≤ R ≤ n，1 ≤ k ≤ R-L+1
如果简单地用暴力法查询，可以先对区间[L, R]内的元素排序，然后定位到第 k k k小的元素，复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。 m m m次查询的总复杂度是 O ( m n l o g n ) O(mnlogn) O(mnlogn)。
能否用线段树求解？线段树特别适合处理区间问题，例如做区间和、区间最值的修改和查询，一次操作的复杂度是 O ( l o g n ) O(logn) O(logn)的。在“线段树”这一节曾指出，这些问题的特征是大区间的解可以从小区间的解合并而来。然而区间第 k k k小这种问题，并不满足这种特征，无法直接用线段树。
本题仍可以用线段树，但不是在一个线段树上操作，而是建立很多线段树，其关键是：两个线段树相减得到新线段树，新线段树对应了新区间的解。
下面逐步推出可持久化线段树的解题思路。
以序列{245, 112, 45322, 98988}为例，序列长度 n n n = 4。
（1）离散化。把序列离散化为{2, 1, 4, 3}，离散化后的元素值是1 ~ n n n，离散化不影响查找第 k k k小。做离散化操作的原因后文有解释。如果有重复元素，见后面的解释。
（2）先思考如何用线段树查询区间 [ 1 , i ] [1, i] [1,i]的第 k k k小。即查询的区间是从1个元素到第i个元素。
对一个确定的 i i i，首先建立一棵包含区间 [ 1 , i ] [1, i] [1,i]内所有元素的线段树，然后在这棵树上查询第 k k k小，复杂度是 O ( l o g n ) O(logn) O(logn)的。
对每个 i i i，都建立一棵区间 [ 1 , i ] [1, i] [1,i]的线段树，共 n n n棵树。查询每个 [ 1 , i ] [1, i] [1,i]区间的第 k k k小，都是 O ( l o g n ) O(logn) O(logn)的。
下面的图，分别是区间[1, 1]、[1, 2]、[1, 3]、[1, 4]的线段树，为了统一，把4个线段树都设计成一样大，即可容纳 n n n = 4个元素的线段树。圆圈内部的数字，表示这个区间内有多少个元素，以及它们在哪些子树上。把圆圈内的值称为结点的权值，整棵树是一棵权值线段树。
图1. 4棵线段树
可以观察到，每棵树与上一棵树只有部分结点不同，就是粗线上的结点，它们是从根到叶子的一条链。
叶子结点的序号实际上就是元素的值，例如叶子[1, 1]表示元素{1}，叶子[2, 2]表示元素{2}，等等。这也是对原序列进行离散化的原因，离散化之后，元素1~ n n n对应了 n n n个叶子。一个结点的左子树上保存了较小的元素，右子树上保存较大的元素。
如何查询区间[1, i]的第k小？例如查询区间[1, 3]的第3小，图(3)是区间[1, 3]的线段树，先查根结点，等于3，说明区间内有3个数；它的左子结点等于2，右子结点等于1，说明第3小数在右子树上；最后确定第3小的数是最后一个叶子，即数字4。查询路径是[1, 4]->[3, 4]->[4, 4]。
（3）查询区间[L, R]的第 k k k小。
如果能得到区间[L, R]的线段树，就能高效率地查询出第 k k k小。根据前缀和的思想，区间[L, R]包含的元素等于区间 [ 1 , R ] [1, R] [1,R]减去区间 [ 1 , L − 1 ] [1, L-1] [1,L−1]。把前缀和思想用于线段树的减法，线段树的减法，是在两棵结构完全的树上，把所有对应结点的权值相减。线段树 R R R减去线段树 L − 1 L-1 L−1，就得到了区间 [ L , R ] [L, R] [L,R]的线段树。
例如区间[2, 4]的线段树，等于把第4个线段树与第1个线段树相减（对应圆圈内的数字相减），得到下图的线段树：
图2. 区间[2, 4]的线段树
观察图中的叶子结点，只有1、3、4这几个叶子结点有值，正好对应区间[2, 4]的元素{1, 3, 4}。
查询区间[2, 4]的第 k k k小，方法与前面查询区间 [ 1 , i ] [1, i] [1,i]的第 k k k小一样。
时间复杂度分析。2个线段树相减，如果对每个结点做减法，结点数量是 O ( n ) O(n) O(n)的，复杂度很高。但是实际上只需要对查询路径上的结点（以及它们的左右子结点）做减法即可，这些结点只有 O ( l o g n ) O(logn) O(logn)个，所以做一次“线段树减法 + 查询第k小”操作，总复杂度是 O ( l o g n ) O(logn) O(logn)的。
（4）存储空间。上述算法的时间复杂度很好，但是需要的存储空间非常大，建立n棵线段树，每棵树的空间是 O ( n ) O(n) O(n)，共需 O ( n 2 ) O(n^2) O(n2)的空间， n = 1 0 5 n = 10^5 n=105时， n 2 n^2 n2 = 10G。
如何减少存储空间？观察这 n n n棵线段树，相邻的2棵线段树，绝大部分结点的值是一样的，只有与新加入元素有关的那部分不同，这部分是从根结点到叶子结点的一条路径，路径上共有 O ( l o g n ) O(logn) O(logn)个结点，只需要存储这部分结点就够了。 n n n棵线段树的总空间复杂度减少到 O ( n l o g n ) O(nlogn) O(nlogn)。
下图演示了建第1棵树的过程。先建一棵原始空树，它是一棵完整的线段树；然后建第1棵树，第1棵树只在原始空树的基础上修改了图(1)中的3个结点，那么只新建这3个结点即可，然后让这3个结点指向原始空树上其他的子结点，得到图(2)的一棵树，这棵树在逻辑上是完整的。
图3 建初始空树和第1棵树
建其他树时，每次也只建与前一棵树不同的 O ( l o g n ) O(logn) O(logn)个结点，并把新建的结点指向前一棵树的子结点，从而在逻辑上仍保持为一棵完整的树。
建树的结果是：共建立了 n n n棵线段树，每棵树在物理上只有 O ( l o g n ) O(logn) O(logn)个结点，但是在逻辑上是一棵完整的线段树。在这些“残缺”的线段树上操作，与在“完整”的线段树上操作相比，效果是一样的。
以上是算法的基本内容，建树的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)，m次查询的时间复杂度是 O ( m l o g n ) O(mlogn) O(mlogn)。
编码的时候，有3个重要的细节：
（1）如何定位每棵线段树。需要建立 n n n棵线段树，这 n n n棵线段树需要方便地定位到，以计算线段树的减法。可以定义一个 r o o t [ ] root[] root[]数组， r o o t [ i ] root[i] root[i]记录第 i i i棵线段树的根结点编号。
（2）初始空树。一般情况下，并不需要真的建一棵初始空树，而是直接从建第1棵树开始。因为空树的结点权值都是0，空树与其他线段树做减法是多余的。在没有初始空树的情况下，建立的 n n n棵线段树不仅在物理上都是“残缺”的，在逻辑上也不一定完整；后面建立的线段树，形态逐渐变得完整。在“残缺”的线段树上做查询，结果仍然是正确的，因为那些在逻辑上也没有的结点不需要纳入计算，可以看成权值为0。不用写建初始空树的代码，能节省一些编码时间。
（3）原始序列中有重复的元素。重复的数字仍需要统计，例如序列{1, 2, 2, 3, 4}，区间[1, 5]的第3小数字是2，不是3。编码时对n个元素离散化，并用 u n i q u e ( ) unique() unique()去重得到 s i z e size size个不同的数字。每个线段树的叶子结点有 s i z e size size个，用 u p d a t e ( ) update() update()建新的线段树时，若遇到重复的元素，累加对应叶子结点的权值以及上层结点的权值即可。用 u p d a t e ( ) update() update()建的线段树总共仍有 n n n个，不是 s i z e size size个。（有网友说“update函数好像会被杭电挂掉”，可以改个函数名）
下面的代码实现了上述算法。其中新建线段树的每个结点，是动态开点。其中的查询函数 q u e r y ( ) query() query()，可以看成在一棵逻辑上完整的线段树上做查询操作。
//洛谷P3834代码, 改写自：https://www.luogu.com.cn/problem/solution/P3834
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 200010;
int cnt = 0; //用cnt标记可以使用的新结点
int a[MAXN], b[MAXN], root[MAXN];
//a[]是原数组,b[]是排序后数组，root[i]记录第i棵线段树的根节点编号
struct{ //定义结点
int L, R, sum; //L左儿子, R右儿子，sum[i]是结点i的权值（即图中圆圈内的数字）
}tree[MAXN<<5]; // <<4是乘16倍，不够用
int build(int pl, int pr){ //初始化一棵空树
int rt = ++ cnt; //cnt为当前节点编号
tree[rt].sum = 0;
int mid=(pl+pr)>>1;
if (pl < pr){
tree[rt].L = build(pl, mid);
tree[rt].R = build(mid+1, pr);
}
return rt; //返回当前节点的编号
}
int update(int pre, int pl, int pr, int x){ //建一棵只有logn个结点的新线段树
int rt = ++cnt; //新的结点，下面动态开点
tree[rt].L = tree[pre].L;//该结点的左右儿子初始化为前一棵树相同位置结点的左右儿子
tree[rt].R = tree[pre].R;
tree[rt].sum = tree[pre].sum + 1; //插了1个数，在前一棵树的相同结点加1
int mid = (pl+pr)>>1;
if (pl < pr){ //从根结点往下建logn个结点
if (x <= mid) //x出现在左子树，修改左子树
tree[rt].L = update(tree[pre].L, pl, mid, x);
else //x出现在右子树，修改右子树
tree[rt].R = update(tree[pre].R, mid+1, pr, x);
}
return rt; //返回当前分配使用的新结点的编号
}
int query(int u, int v, int pl, int pr, int k){ //查询区间[u,v]第k小
if (pl == pr) return pl; //到达叶子结点，找到第k小，pl是节点编号，答案是b[pl]
int x = tree[tree[v].L].sum - tree[tree[u].L].sum; //线段树相减
int mid = (pl+pr)>>1;
if (x >= k) //左儿子数字大于等于k时，说明第k小的数字在左子树
return query(tree[u].L, tree[v].L, pl, mid, k);
else //否则在右子树找第k-x小的数字
return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n); //对b排序
int size = unique(b+1, b+1+n)-b-1; //size等于b数组中不重复的数字的个数
//root[0] = buildtree(1, size); //初始化一棵包含size个元素的空树，实际上无必要
for (int i = 1; i <= n; i ++){ //建n棵线段树
int x = lower_bound(b+1, b+1+size, a[i]) - b;
//找等于a[i]的b[x]。x是离散化后a[i]对应的值
root[i] = update(root[i-1], 1, size, x);
//建第i棵线段树，root[i]是第i棵线段树的根结点
}
while (m--){
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
int t = query(root[x-1], root[y], 1, size, k);
//第y棵线段树减第x-1棵线段树，就是区间[x,y]的线段树
printf("%d\n", b[t]);
}
return 0;
}
需要分配的空间是 O ( n l o g n ) O(nlogn) O(nlogn)，具体是多少？在线段树这一节曾指出，一棵线段树需要分配 4 n 4n 4n个结点，那么总空间约为 n l o g ( 4 n ) nlog(4n) nlog(4n)，题目给定 n = 200000 n = 200000 n=200000， l o g ( 4 n ) ≈ 20 log(4n) ≈ 20 log(4n)≈20，代码中定义的 t r e e [ M A X N < < 5 ] tree[MAXN<<5] tree[MAXN<<5]够用。
区间第 k k k大问题的另一种解法是莫队算法，见上一节“分块与莫队算法”。
2. 区间内小于等于k的数字有多少
Super Mario hdu 4417
题目描述：给定一个整数序列，有n个数。有m个询问，询问区间[L,R]内小于k的整数有多少个。
输入：第一行是整数T，表示测试用例个数。对每个测试，第一行是整数n,m。下一行是n个整数a1, a2, …, an，后面有m行，每行有3个整数L、R、k。
输出：对每个测试用例，输出m行，每行是一个询问的答案。
数据范围：1 ≤ n, m ≤ 105, 0 ≤ ai ≤ 1 0 5 10^5 105, 1 ≤ L ≤ R ≤ n，1 ≤ ai, k ≤ 1 0 9 10^9 109
“区间内小于等于 k k k的数字有多少”问题与“区间第 k k k小”问题很相似。
（1） u p d a t e ( ) update() update()函数，建 n n n棵线段树，与例题“洛谷P3834”的代码一样。线段树的每个结点的权值是这棵子树下叶子结点的权值之和。
（2） q u e r y ( ) query() query()函数，统计区间 [ L , R ] [L, R] [L,R]内小于等于 k k k的数字有多少个。首先用线段树减法（线段树 R R R减去线段树 L − 1 L-1 L−1）得到区间 [ L , R ] [L, R] [L,R]的线段树，然后统计这棵树上比 k k k小的数字即可，统计方法就是标准的线段树“区间和”查询。例如图2，它是{1, 3, 4}的线段树，如果求小于等于 k k k=3的数字有多少，答案就是求这棵线段树的区间[1, 3]的区间和，它等于[1, 2]区间和加上[3, 3]区间和。同样，这里做线段树的减法，并不需要把每个结点相减，只需要对查询路径上的结点做减法（即结点[3, 3]和结点[1, 2]），只涉及到 O ( l o g n ) O(logn) O(logn)个结点。
3. 区间内有多少不同的数字
Sequence II hdu 5919
题目描述：一个整数序列，有n个数A[1], A[2], …, A[n]。做m次询问，第i个询问，给定两个整数Li、Ri，表示一个区间，区间内是一个子序列，其中不同的整数有ki个，输出第ki/2个整数在这个子序列中第一次出现的位置。
输入：第一行是整数T，表示测试用例个数。对每个测试，第一行是2个整数n和m，下面一行是n个整数，表示序列。后面m行，每行有两个整数Li、Ri。
输出：对每个测试，输出一行，包括m个回答。
数据范围：1 ≤ n, m ≤ 2* 1 0 5 10^5 105, 0 ≤ A[i] ≤ 1 0 5 10^5 105
首先求区间内有多少个不同的数字。若按前面建主席树的方法，第 i i i棵主席树记录区间 [ 1 , i ] [1, i] [1,i]内的数字情况，如何定义叶子结点的权值？考虑2种方案：
（1）叶子结点的权值是这个数字出现的次数。那么查询区间 [ L , R ] [L, R] [L,R]内不同数字个数时，用线段树 R R R减去线段树 L − 1 L-1 L−1，得到区间 [ L , R ] [L,R] [L,R]的线段树，此时每个叶子结点的权值是这个数字在区间内 [ L , R ] [L,R] [L,R]出现的次数。在这棵线段树上，无法以 O ( l o g n ) O(logn) O(logn)的复杂度计算不同的数字个数。
（2）叶子结点的权值等于1，表示这个数字在区间 [ 1 , i ] [1, i] [1,i]出现过；等于0，表示没有出现过。这样做可以去重，但是无法用线段树减法来计算区间的不同数字个数。例如，区间 [ 1 , L − 1 ] [1, L-1] [1,L−1]内出现某个数字，区间 [ L , R ] [L, R] [L,R]内再次出现这个数字，它们对应的叶子结点权值都是1；对线段树 R R R和 L − 1 L-1 L−1做减法后，得到 [ L , R ] [L, R] [L,R]区间的线段树，这个叶子结点的权值是0，表示这个数字不存在，而区间 [ L , R ] [L, R] [L,R]内其实是有这个数字的。
这题仍可以用主席树，但是需要使用新的技巧：倒序建立这 n n n棵线段树。
（1）每棵线段树的叶子结点有 n n n个。这与例题“洛谷P3834”的线段树不同。第 i i i个叶子结点记录第 i i i个元素是否出现。
（2）按倒序建立线段树。一个元素建立一棵线段树，用第 n n n个元素 A [ n ] A[n] A[n]建立第1个线段树，用第 n − 1 n-1 n−1个元素 A [ n − 1 ] A[n-1] A[n−1]建立第2个线段树…，共有 n n n棵线段树。用元素 A [ n ] A[n] A[n]建立第1棵线段树时，第n个叶子结点的权值是1；…；建立第 i − 1 i-1 i−1棵线段树时，若 A [ i − 1 ] A[i-1] A[i−1]在区间 [ i , n ] [i, n] [i,n]中曾出现过，将第 i i i个叶子结点的权值置为0，然后把第 i − 1 i-1 i−1个叶子结点权值记为1。这个操作把重复的元素从第 i − 1 i-1 i−1个线段树中剔除，只在第1次出现的叶子结点位置记录权值。如何编程实现？可以定义 m p [ ] mp[] mp[]数组， m p [ A [ i ] ] = i mp[A[i]] = i mp[A[i]]=i，表示元素 A [ i ] A[i] A[i]在第i个线段树的第 i i i个叶子结点出现；建第 k k k个线段树时，若 m p [ A [ k ] ] > 0 mp[A[k]] > 0 mp[A[k]]>0，说明 A [ k ] A[k] A[k]这个元素曾出现过，先把第 k k k个线段树的第 m p [ A [ k ] ] mp[A[k]] mp[A[k]]个叶子结点权值置为0，然后把第 k k k个叶子结点权值置为1。
（3）查询区间 [ L , R ] [L, R] [L,R]内不同数字个数。第 L L L棵线段树，只记录了 A [ L ] A[L] A[L] ~ A [ n ] A[n] A[n]区间内不同数字的情况，而不包括 A [ 1 ] A[1] A[1] ~ A [ L − 1 ] A[L-1] A[L−1]，那么只需要在第 L L L棵线段树上，按标准的区间查询操作计算 [ 1 , R ] [1, R] [1,R]的区间和，就是答案。
题目要求输出区间[ L , R ] L, R] L,R]内第 k / 2 k/2 k/2个整数在这个区间中第一次出现的位置，由于第 L L L棵线段树记录的就是 A [ L ] A[L] A[L] ~ A [ n A[n A[n]第1次出现的位置，那么只需要在这棵线段树上查询 [ 1 , R ] [1, R] [1,R]的第 k / 2 k/2 k/2个叶子结点即可。
4. 区间更新
To the moon hdu 4348 区间更新
题目描述：给定n个整数A[1], A[2], …, A[n]，执行m个操作，有以下几种操作：
- C L R d 区间[L, R]每个A[i]加上d，时间 t t t加1，注意只有这个操作才会改变 t t t，第1个操作 t t t=1。
- Q L R 查询区间和
- H L R t 查询时间t的历史区间和
- B t 返回时间t，t以后的操作全部清空
1 ≤ n, m ≤ 105, |A[i]| ≤ 1 0 9 10^9 109, 1 ≤ L ≤ R ≤ n，|d|≤ 1 0 4 10^4 104
若没有时间 t t t，只需要建一棵线段树，就是标准的线段树模板题。加上时间点 t t t后，每个时间点建一棵线段树，这正符合主席树的标准应用，按标准的主席树编码即可。
习题
区间第k大：hdu2665
可持久化数组：洛谷 P3919
主席树专题训练：https://www.cnblogs.com/HDUjackyan/p/9069311.html
带修改的主席树：ZOJ 2112 Dynamic Rankings
