主席树（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);
}
}
}