主席树：从“区间求和”到“可持久化”的线段树进阶

引言

普通线段树能高效地维护一个数组的动态变化，但它有一个“致命缺陷”：修改会覆盖历史。当你更新了某个节点，之前版本的数据就永远丢失了。

如果问题是：给定一个序列，每次查询某个历史版本的状态怎么办？或者更经典一些——查询区间 [L, R] 中第 k 小的数，你会发现普通线段树完全无能为力。

主席树（可持久化线段树） 的出现就是为了解决这个问题。它的核心思想是：每次修改只新建被影响的那条链上的节点，其余节点与上一版本共用。这样，每个历史版本的根节点都被保存下来，你可以随时“回到过去”查询任意版本的数据。

如果把普通线段树比作“在黑板上写字，擦了就没了”，那么主席树就是 “每次修改都拍一张快照，只记录变化的部分”——你拥有了整条时间线，可以随时穿越回任意历史时刻。

前置知识

在学习主席树之前，你需要掌握以下内容：

第一章：从“问题”到“思想”——主席树是什么？

1.1 一个经典问题：静态区间第 k 小

给定长度为 n 的序列，m 次询问，每次查询区间 [L, R] 中第 k 小的数。

如果只查一次全局的第 k 小，排序即可。但每次查询的区间都不同，怎么办？

朴素思路：对每个位置 i，建一棵线段树维护 [1, i] 的权值信息。查询 [L, R] 时，用第 R 棵树减去第 L-1 棵树，得到区间内的权值分布，然后在线段树上二分找第 k 小。

但暴力建 n 棵完整的线段树，空间是 O(n²)，不可行。

1.2 主席树的“省空间”魔法

仔细观察：从第 i-1 棵树到第 i 棵树，我们只插入了一个新元素。权值线段树中，这个修改只会影响从根到对应叶子节点的一条路径，共 O(log n) 个节点。

主席树的策略是：

• 新建一个根节点 root[i]。

• 从 root[i] 开始，沿着插入值对应的路径，新建这条路径上的所有节点。

• 路径之外的节点，直接指向上一版本 root[i-1] 中对应的节点。

这样，每插入一个元素只新建 O(log n) 个节点，总空间 O(n log n)。

可以把主席树想象成一棵“有很多根”的树。每个根对应一个版本，版本之间共享大部分节点。查询时从对应的根出发，就像进入了那个版本的“平行宇宙”。

第二章：算法步骤与代码实现

2.1 数据结构定义

主席树采用动态开点，不能用堆式存储（2x、2x+1）。我们需要用数组记录每个节点的左右儿子和权值：

const int MAXN = 200005;
const int MAXT = MAXN * 40; // n log n 级别，通常开 n << 5

int root[MAXN]; // 每个版本的根节点编号
int ls[MAXT], rs[MAXT]; // 左右儿子
int sum[MAXT]; // 该节点维护的权值出现次数
int tot = 0; // 节点总数

2.2 建树（空树）

先建一棵空的权值线段树，所有节点的 sum 都为 0。这是所有版本的“基准”：

int build(int l, int r) {
int now = ++tot;
if (l == r) return now;
int mid = (l + r) >> 1;
ls[now] = build(l, mid);
rs[now] = build(mid + 1, r);
return now;
}

2.3 修改（插入一个值）

在上一版本 pre 的基础上，插入值 pos，新建一条链：

int modify(int pre, int l, int r, int pos) {
int now = ++tot;
ls[now] = ls[pre];
rs[now] = rs[pre];
sum[now] = sum[pre] + 1; // 当前节点多了一个数

if (l == r) return now;

int mid = (l + r) >> 1;
if (pos <= mid) ls[now] = modify(ls[pre], l, mid, pos);
else rs[now] = modify(rs[pre], mid + 1, r, pos);

return now;
}

关键点：

• 新建节点 now 先拷贝上一版本 pre 的左右儿子和 sum。

• sum[now] = sum[pre] + 1 表示当前值域区间多了一个数。

• 递归修改对应子树，另一棵子树直接沿用 pre 的节点。

• 每层只新建一个节点，共新建 O(log n) 个节点。

2.4 查询（区间第 k 小）

查询 [L, R] 的第 k 小，同时从 root[R] 和 root[L-1] 向下走：

int query(int u, int v, int l, int r, int k) {
// u = root[R], v = root[L-1]
if (l == r) return l; // 找到第 k 小对应的离散化值

int mid = (l + r) >> 1;
// 左子树中 [L, R] 区间的数的个数
int left_cnt = sum[ls[u]] – sum[ls[v]];

if (k <= left_cnt) return query(ls[u], ls[v], l, mid, k);
else return query(rs[u], rs[v], mid + 1, r, k – left_cnt);
}

关键点：

• sum[ls[u]] – sum[ls[v]] 得到区间 [L, R] 内落在左值域区间的数的个数。

• 如果 k <= left_cnt，第 k 小在左子树；否则在右子树找第 k – left_cnt 小。

2.5 完整的主函数流程

int main() {
int n, m;
cin >> n >> m;

vector<int> a(n + 1);
vector<int> vals;
for (int i = 1; i <= n; i++) {
cin >> a[i];
vals.push_back(a[i]);
}

// 离散化
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());

root[0] = build(1, vals.size());

for (int i = 1; i <= n; i++) {
int pos = lower_bound(vals.begin(), vals.end(), a[i]) – vals.begin() + 1;
root[i] = modify(root[i – 1], 1, vals.size(), pos);
}

while (m–) {
int L, R, k;
cin >> L >> R >> k;
int ans_pos = query(root[R], root[L – 1], 1, vals.size(), k);
cout << vals[ans_pos – 1] << '\\n';
}
return 0;
}

空间提醒：节点数上限一般为 n * (log2(n) + 1) + 4n，大约 n << 5 即可。如果 n 达到 2e5，MAXT = MAXN * 40 是安全值。

第三章：复杂度与性质

其中 V 是值域大小（离散化后为元素个数）。

关键性质：

• 可持久化：每个历史版本的根节点 root[i] 都被保存，可以查询任意版本。

• 可减性：主席树维护的信息满足区间减法，因此可以用两个版本“相减”得到任意区间的信息。

• 静态 vs 动态：上述实现是静态主席树——所有数据预先知道，只查询不修改。如果需要支持修改，需要套上树状数组，即动态主席树。

第四章：例题与详细解析

例题1：【模板】可持久化线段树 1（主席树）—— 洛谷 P3834

题目描述
给定 n 个整数构成的序列，m 次查询，每次查询区间 [L, R] 内的第 k 小值。

输入示例

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出示例

6405
15770
26287
25957
26287

解题思路
这就是主席树的模板题，直接套用上面的完整代码即可。

详细解析

第一步：理解数据
序列长度为 5，值为 [25957, 6405, 15770, 26287, 26465]。离散化后，这些值分别对应 [3, 1, 2, 4, 5]。

第二步：构建版本

• root[0]：空树，所有节点 sum = 0。

• root[1]：插入 25957（离散化值 3）。新建从根到叶子 3 的路径（共 log 5 ≈ 3 个节点）。

• root[2]：在 root[1] 基础上插入 6405（离散化值 1）。新建从根到叶子 1 的路径，其他节点指向 root[1]。

• 依此类推，得到 5 个版本的根节点。

第三步：查询 [2, 2] 的第 1 小

• 用 root[2] – root[1] 得到只包含第 2 个元素的权值线段树。

• 在树上二分找第 1 小，得到离散化值 1，对应原值 6405。

第四步：查询 [3, 4] 的第 1 小

• 用 root[4] – root[2] 得到区间 [3, 4] 的权值分布：元素为 [15770, 26287]。

• 第 1 小是 15770。

复杂度：建树 O(n log n)，每次查询 O(log n)，总复杂度 O((n+m) log n)。

代码要点：

• 离散化时用 sort + unique + lower_bound。

• root[0] = build(1, cnt) 建空树，所有 sum 默认为 0。

• 查询时两个指针 u 和 v 同时移动。

例题2：树上主席树 —— 洛谷 P2633 Count on a tree

题目描述
给定一棵 n 个节点的树，每个点有一个权值。m 次询问，每次给出 u, v, k，回答 u 到 v 路径上第 k 小的点权。

输入示例

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

输出示例

2
5
8
105
7

解题思路
这道题将主席树从序列搬到了树上。

关键在于：树上的一条路径可以拆成四个前缀。

设 root[u] 表示从根节点到 u 的路径上所有点权构成的权值线段树。那么：

• 从根到 u 的版本：root[u]

• 从根到 v 的版本：root[v]

• 从根到 LCA(u, v) 的版本：root[lca]

• 从根到 LCA 的父节点的版本：root[fa[lca]]

路径 u → v 上的权值分布 = root[u] + root[v] – root[lca] – root[fa[lca]]。

查询第 k 小时，四个指针同时移动，用这个公式计算左子树的节点数。

详细解析

第一步：树上 DFS 建树
从根节点 1 开始 DFS，每访问一个节点 u，就在父版本的基础上插入 a[u]，得到 root[u]。

void dfs(int u, int fa) {
depth[u] = depth[fa] + 1;
up[u][0] = fa;
root[u] = modify(root[fa], 1, cnt, get_id(a[u]));
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
}
}

第二步：查询路径 [u, v] 的第 k 小

int lca = get_lca(u, v);
int fa_lca = up[lca][0];
// 四个版本同时查
int left_cnt = sum[ls[root[u]]] + sum[ls[root[v]]]
– sum[ls[root[lca]]] – sum[ls[root[fa_lca]]];

如果 k <= left_cnt，四个指针都走向左子树；否则走向右子树，k -= left_cnt。

第三步：LCA 预处理
用倍增法预处理 up[u][i]，支持 O(log n) 查询 LCA。

复杂度：预处理 O(n log n)，每次查询 O(log n)。

例题3：动态主席树（带修改）—— 洛谷 P2617 Dynamic Rankings

题目描述
给定一个序列，支持两种操作：

• Q i j k：查询区间 [i, j] 中第 k 小的数。

• C i t：将 a[i] 修改为 t。

输入示例

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

输出示例

3
6

解题思路
静态主席树无法处理修改，因为修改一个位置会影响从该位置往后的所有版本（前缀和性质被破坏）。

解决方案：树状数组套主席树。

• 树状数组的每个节点 i 维护一棵权值线段树，表示 [i – lowbit(i) + 1, i] 区间内的元素分布。

• 修改 a[pos] 时，更新树状数组上所有包含 pos 的节点（O(log n) 个），每个节点在权值线段树上修改（O(log n)），总复杂度 O(log² n)。

• 查询 [L, R] 时，将 R 和 L-1 分别拆成 O(log n) 个树状数组节点，收集这些节点的根，同时计算左子树大小。

详细解析

第一步：离散化
所有初始值和修改中出现的值都要参与离散化。

第二步：树状数组维护线段树根

int tree[MAXN]; // tree[i] 是树状数组节点 i 对应的线段树根
void add(int idx, int pos, int delta) {
for (int i = idx; i <= n; i += i & -i) {
modify(tree[i], 1, tot, pos, delta);
}
}

第三步：查询

int query(int l, int r, int k) {
// 收集 R 对应的节点到 vecR，L-1 对应的节点到 vecL
for (int i = r; i > 0; i -= i & -i) vecR.push_back(tree[i]);
for (int i = l – 1; i > 0; i -= i & -i) vecL.push_back(tree[i]);
// 二分查找第 k 小
while (l < r) {
int left_sum = 0;
for (int root : vecR) left_sum += sum[ls[root]];
for (int root : vecL) left_sum -= sum[ls[root]];
if (k <= left_sum) { /* 全部走向左子树 */ }
else { /* 走向右子树，k -= left_sum */ }
}
}

复杂度：修改 O(log² n)，查询 O(log² n)，空间 O((n+m) log² n)。

例题4：主席树 + 二分答案 —— 洛谷 P4587 [FJOI2016] 神秘数

题目描述
给定序列，每次询问区间 [L, R]，求最小的不能由区间内任意子集和表示的正整数。

解题思路
这是一个巧妙的转化题。

核心性质：假设当前能表示的数的范围为 [1, x]，那么下一个能扩展范围的数是所有 ≤ x+1 的数的和。如果这些数的和 > x，则范围可以扩展；否则 x+1 就是答案。

主席树的作用：快速查询区间 [L, R] 中值域在 [1, x+1] 内的所有数的和。

算法流程：

每次查询 O(log n)，最多扩展 O(log n) 次（因为 ans 至少翻倍），总复杂度 O(log² n)。

第五章：主席树的常见变形与应用场景

总结

主席树（可持久化线段树）通过“每次修改只新建一条链，其余节点共用”的巧妙设计，将“多版本线段树”的空间从 O(n²) 降到了 O(n log n)。它利用前缀和的可减性，能在 O(log n) 内回答任意区间的权值统计问题。

学习主席树的三个关键点：