主席树（Persistent Segment Tree）通过对每次修改保留历史版本，实现"查询第 k 个版本中某区间的值"。最经典应用是静态区间第 k 小。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph TD A[修改] --> B[复制路径节点] B --> C[共享未改子树] C --> D[多版本并存]
每次修改不覆盖旧节点，而是新建被修改路径上的节点，共享未修改部分。
版本0: [1,8]
/ \
[1,4] [5,8]
/ \ / \
[1,2][3,4][5,6][7,8]
修改位置3后（版本1）：
[1,8]' ← 新根
/ \
[1,4]' [5,8] ← 右子树共享
/ \
[1,2] [3,4]' ← 只有路径上新建
- 每次修改新建 O(log n) 个节点
- n 次操作总空间 O(n log n)
二、静态区间第 k 小
问题
给定数组，多次查询 [l, r] 中第 k 小的值。
思路
- 离散化原数组
- 对每个前缀
[1, i]建一棵权值线段树（版本 i） - 查询
[l, r]= 版本 r - 版本 l-1（差分） - 在差分树上二分找第 k 小
实现
public class PersistentSegTree {
int[] left, right, sum;
int[] roots;
int tot;
public PersistentSegTree(int n, int q) {
int maxNodes = (n + q) * 20; // n log n
left = new int[maxNodes];
right = new int[maxNodes];
sum = new int[maxNodes];
roots = new int[n + 1];
tot = 0;
}
// 在前一版本基础上，给 pos 位置 +1
int update(int prev, int l, int r, int pos) {
int cur = ++tot;
left[cur] = left[prev];
right[cur] = right[prev];
sum[cur] = sum[prev] + 1;
if (l == r) return cur;
int mid = (l + r) / 2;
if (pos <= mid) left[cur] = update(left[prev], l, mid, pos);
else right[cur] = update(right[prev], mid + 1, r, pos);
return cur;
}
// 查询第 k 小（rootR - rootL 的差分）
int query(int rootL, int rootR, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) / 2;
int leftCount = sum[left[rootR]] - sum[left[rootL]];
if (k <= leftCount) {
return query(left[rootL], left[rootR], l, mid, k);
} else {
return query(right[rootL], right[rootR], mid + 1, r, k - leftCount);
}
}
}使用
// 离散化
int[] sorted = arr.clone();
Arrays.sort(sorted);
int m = unique(sorted);
// 建 n 个版本
for (int i = 1; i <= n; i++) {
int pos = lowerBound(sorted, m, arr[i]) + 1;
roots[i] = update(roots[i - 1], 1, m, pos);
}
// 查询 [l, r] 第 k 小
int idx = query(roots[l - 1], roots[r], 1, m, k);
int answer = sorted[idx - 1];三、复杂度
| 操作 | 时间 | 空间 |
|---|---|---|
| 建树（n 个版本） | O(n log n) | O(n log n) |
| 单次查询 | O(log n) | — |
四、主席树 vs 其他方案
| 方案 | 区间第 k 小 | 修改 |
|---|---|---|
| 排序 + 暴力 | O(n log n) 每次 | — |
| 归并树 | O(log³n) | 不支持 |
| 主席树 | O(log n) | 不支持（静态） |
| 树套树 | O(log²n) | 支持 |
五、面试要点
- 路径复制：只新建被修改的 O(log n) 个节点，其余共享
- 前缀差分：版本 r - 版本 l-1 得到 [l, r] 的信息
- 离散化：值域压缩到 [1, n]
- 空间估算：n × (log₂n + 1) 个节点
- LeetCode：无直接题，但思想用于“可持久化并查集”等
六、路径复制过程模拟
以对 [1, 3, 2] 建主席树，插入第 2 个元素（值 3 → 版本2）为例：
值域离散化后为 [1, 3]，线段树维护“值域区间内出现次数”
版本1（插入值1）： 版本2（再插入值3）：
[1,3]:1 [1,3]:2 ← 新建
/ \ / \
[1,2]:1 [3,3]:0 [1,2]:1 [3,3]:1 ← 新建
/ \ (空) (共享) (空)
[1,1]:1 [2,2]:0
关键：从根到叶 [3,3] 的路径上节点全部新建（O(log n) 个），
其余节点（如 [1,2]:1 子树）直接共享版本1 的指针
空间：每次插入只新增 log₂(值域)+1 个节点，而非整棵 O(值域)
查询区间 [l, r] 内第 k 小：
用“版本 r 的树 - 版本 l-1 的树”做差分：
在值域线段树上，左子树的差分值 = 区间内落在左半值域的元素个数
若差分值 ≥ k → 答案在左子树，否则去右子树找第 k-左计数 小
例：数组 [1,3,2,4]，查询 [2,4] 第 2 小：
版本4 - 版本1 的树 → 统计值在 [2,4] 的元素 {3,2,4}
左子树[1,2]计数=1 < 2 → 去右子树找第 2-1=1 小 → 3 ✓
七、思考题
- 为什么主席树能用“版本差分”求任意区间 [l, r] 的信息？这依赖什么性质？（提示：前缀和的可减性）
- 如果每次修改都复制整棵树，空间复杂度是多少？路径复制如何优化到 O(n log n)？（提示：只有 O(log n) 个节点被影响）
- 主席树能否支持“区间修改”？为什么懒标记会带来困难？（提示：共享节点被多个版本引用，打标记会互相污染）