可持久化线段树（主席树）：时光倒流的区间查询
较难6可持久化线段树（主席树）：给数据装一台“时光机”
你有没有想过，如果写错了题目能回到之前的状态重来就好了？可持久化线段树就给了数据一种“后悔药”：每一次修改都会生成一个新版本，同时保留旧版本，你可以随时访问任意历史版本的数据。因为发明者黄嘉泰（HJT）名字缩写像“主席”，所以常被称为主席树。
生活中的“时间旅行”
想象一下，你正在用铅笔写数学作业，每做完一题就想拍张照片保存。如果后面写错了，你可以擦掉重写，但是还能翻出之前拍的照片看看原来是怎么写的。主席树就是给每个历史时刻拍了一张“快照”。
更贴近你的生活：打游戏时，你常常会在打Boss前手动存档，万一打不过就读取存档重来。主席树允许你在数组上做这样的操作——每次修改（比如把某个位置的值改掉）都会生成一个新版本，而旧版本依然存在。你可以随时查询任意版本中任意区间里的信息。
核心思想：只新增，不复用旧节点
普通的线段树一次修改需要修改从根到叶子的整条路径上所有节点，代价是O(log N)。如果每次修改都完整复制一棵树，那空间和时间都爆炸。主席树的高明之处在于：每次修改只新建路径上的 log N 个节点，其余节点继续延用旧版本的指针。这样一来，每修改一次只增加 O(log N) 的空间，总空间为 O(N log N)。
从生活看空间节省
假设你有N个同学，每个同学手里有一份全班成绩单（存着身高数据）。如果每个人都在自己的那份上修改一个数，普通做法是每人抄整份成绩单，成本太高。主席树的做法是：第一个人拿着原始成绩单，第二个人只把修改的那个数字所在的那一行重写一遍，然后指着第一份的其他行说“那些行还是原来的”。第三个人又在第二份的基础上只重写自己改的那一行……这样所有成绩单共用大部分行，省下了很多纸。
最常见应用：静态数组的区间第K小（大）值
主席树最经典的应用就是求一个固定数组的任意区间 [l, r] 中，第 k 小的数是多少。注意这里数组的值之后不会修改（称为“静态”），但我们有多次查询，每次区间和 k 都不同。
核心做法：前缀和 + 差分
- 将原数组的值离散化（把数值映射到 1~M，M 是不同数值个数）。
- 对数组的每个前缀 i（即前 i 个数）建立一棵值域线段树：这棵树存的是前 i 个数中，每个数值出现的次数（即桶）。树中每个节点 [L,R] 表示这个前缀里数值在 [L,R] 之间的数有多少个。
- 要查询区间 [l, r] 的信息，用前缀 r 的树减去前缀 l-1 的树，就能得到区间内每个数值的个数。这就是“差分”思想，像这样：
sum_in_interval = tree[r] - tree[l-1]。 - 然后在差值树上找第 k 小：如果左子树中的总数（区间内数值范围在左半边的数的个数）>= k，则答案在左半边；否则在右半边，此时 k 减去左子树的个数。
为什么叫“主席树”？
因为每个前缀一棵树，就像每个主席（校长）都有自己的档案柜；而树之间通过共享节点形成一种“可持久化”结构，名字便由此而来。
手把手理解代码：求区间第K小（离散化后）
下面这段代码实现了上面说的过程。请逐行看注释，理解每一步。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005; // 数组最大长度
struct Node {
int l, r, sum; // l:左孩子节点编号, r:右孩子节点编号, sum:该节点代表的区间内的数值个数
} t[MAXN * 20]; // 主席树节点数组，开20倍左右（通常N*4*logN够用）
int root[MAXN], cnt; // root[i]:第i个版本的树根节点编号, cnt:当前已创建的节点总数
int n, q; // n:数组长度, q:查询次数
int arr[MAXN]; // 原数组（1-indexed）
vector<int> v; // 用于离散化的有序向量（存放所有出现过的数值）
// 建立一棵空的值域线段树，返回根节点编号
int build(int l, int r) {
int p = ++cnt; // 生成新节点编号
t[p].sum = 0; // 初始个数为0
if (l == r) return p; // 叶子节点直接返回
int mid = (l + r) / 2;
t[p].l = build(l, mid);
t[p].r = build(mid+1, r);
return p;
}
// 更新：基于前一个版本pre，在位置pos上增加一个数（数值对应的离散化下标）
// 返回新版本根节点编号
int update(int pre, int l, int r, int pos) {
int p = ++cnt; // 新建当前节点
t[p] = t[pre]; // 先复制旧节点的左右孩子指针和sum
t[p].sum++; // 当前区间多了一个数
if (l == r) return p; // 叶子节点更新完毕
int mid = (l + r) / 2;
if (pos <= mid)
t[p].l = update(t[pre].l, l, mid, pos); // 左子树新建，右子树继续沿用旧版本
else
t[p].r = update(t[pre].r, mid+1, r, pos); // 右子树新建
return p;
}
// 查询区间第k小：u对应前l-1个数的版本，v对应前r个数的版本
// 在值域[l,r]内找第k小的数值的离散化下标
int query(int u, int v, int l, int r, int k) {
if (l == r) return l; // 找到了叶子，返回该数值的离散化下标
int mid = (l + r) / 2;
int leftSum = t[t[v].l].sum - t[t[u].l].sum; // 左子树在区间内的个数 = v的左子树个数 - u的左子树个数
if (k <= leftSum)
return query(t[u].l, t[v].l, l, mid, k);
else
return query(t[u].r, t[v].r, mid+1, r, k - leftSum);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
v.push_back(arr[i]); // 收集所有数值用于离散化
}
// 离散化：排序 + 去重
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// 建立第0个版本（空树），所有值出现次数为0
root[0] = build(1, v.size());
// 依次插入每个数，生成第i个版本
for (int i = 1; i <= n; i++) {
// pos是arr[i]在离散化后的下标（从1开始）
int pos = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
root[i] = update(root[i-1], 1, v.size(), pos);
}
// 处理查询
while (q--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int idx = query(root[l-1], root[r], 1, v.size(), k);
printf("%d\n", v[idx-1]); // 将离散化下标转回原数值
}
return 0;
}
代码中的常见“坑”和注意点
- 节点数组大小要开够：一般开
MAXN * 20或MAXN * (log2(MAXN)+2)。如果忘了开大，会因数组越界导致奇怪错误（比如 RE 或 WA）。 - 离散化是必须的：值域线段树要求值域范围在可接受的区间内（比如 1~1e5）。如果直接用原数值，可能值域特别大（如 10^9），线段树节点会爆炸。
- 注意下标是1-indexed还是0-indexed：我们代码中用1-indexed，arr[1]~arr[n]，root[0]表示空前缀。query中
root[l-1]和root[r]对应左闭右开区间。 - 查询时
k - leftSum的位置：当进入右子树时，k必须减去左子树的总数，因为左子树已经包含了前leftSum个小的数。 - 空间回收？不需要：主席树创建的所有节点一直保留，因为每个历史版本都可能被查询。所以不用担心内存泄漏，只要节点数组开够就行。
- 多组数据时要重置cnt和root[0]：如果有多组测试数据，每次开始前记得
cnt=0;并重新建空树。
扩展：可持久化线段树还能做什么？
- 动态区间第K小：结合树状数组（BIT）或线段树套主席树，可以实现支持修改的区间第K小（树套树）。
- 可持久化数组：直接用主席树实现一个可以回退版本的一维数组，每个叶子存一个值。每次修改只新建一条路径。
- 可持久化并查集：把并查集的 fa 数组和 size 数组用可持久化数组实现，就能得到支持历史版本查询的并查集。
- 统计区间内不同数的个数：用主席树维护每个数上一次出现的位置，也能巧妙求解。
相关知识点指引
- 线段树（普通版）：主席树的基础，必须先掌握普通线段树的建树、更新、查询。
- 二分答案 + 值域线段树：如果把主席树换成每次二分值域，也可以求区间第K小，但会慢很多。
- 树套树：如线段树套平衡树，也能解决动态区间第K小，但常数大、代码长。
- 可持久化Trie（字典树）：思路类似，常用于解决二进制异或相关的问题（如最大异或和）。
主席树让区间查询拥有了“时间旅行”的能力，是处理历史数据的经典方法。学会它，你就多了一把解决区间统计问题的利器。动手写代码，多跑几个样例试试吧！
例题精讲
可持久化线段树（主席树）的核心特点是什么？
在构建可持久化线段树时，每次插入一个数需要新建 O(log n) 个节点。
以下为主席树查询区间第 k 小的核心递归代码，补全缺失部分。
int query(int u, int v, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int left = tree[tree[u].l].sum - tree[tree[v].l].sum;
if (k <= left)
return query(tree[u].l, tree[v].l, l, mid, k);
else
return query(tree[u].r, tree[v].r, mid + 1, r, ___);
}