1. 什么是可持久化线段树

可持久化线段树（Persistent Segment Tree），又称主席树，是一种能够保存历史版本的数据结构。它在普通线段树的基础上，通过复用未修改的节点来创建新的版本，从而在O(log n)的时间复杂度内支持对历史版本的查询和修改。

2. 核心思想

可持久化线段树的核心思想是节点复用：当修改某个节点时，只创建该节点的新副本，而其他未修改的节点则直接指向旧版本的节点。这样每个版本都对应一棵完整的线段树，但不同版本之间共享了大量节点。

3. 数据结构设计

每个节点需要存储以下信息：

• 左子节点指针
• 右子节点指针
• 节点维护的值（如区间和、最大值等）

4. 基本操作

4.1 建树

struct Node { int l, r; // 左右子节点编号 int sum; // 区间和 } tr[N * 40]; // 需要开足够大的空间 int build(int l, int r) { int p = ++idx; if (l == r) { tr[p].sum = a[l]; return p; } int mid = (l + r) >> 1; tr[p].l = build(l, mid); tr[p].r = build(mid + 1, r); tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum; return p; }

4.2 单点更新

int update(int pre, int l, int r, int pos, int val) { int p = ++idx; tr[p] = tr[pre]; // 复制原节点 if (l == r) { tr[p].sum = val; return p; } int mid = (l + r) >> 1; if (pos <= mid) tr[p].l = update(tr[pre].l, l, mid, pos, val); else tr[p].r = update(tr[pre].r, mid + 1, r, pos, val); tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum; return p; }

4.3 区间查询

int query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return tr[p].sum; int mid = (l + r) >> 1, res = 0; if (ql <= mid) res += query(tr[p].l, l, mid, ql, qr); if (qr > mid) res += query(tr[p].r, mid + 1, r, ql, qr); return res; }

5. 经典应用

5.1 静态区间第k小

这是主席树最经典的应用。通过对值域建立可持久化线段树，每个版本对应前缀[1, i]中各个数值出现的次数。

5.2 可持久化数组

支持历史版本的数组单点修改和查询。

5.3 树上路径查询

结合树链剖分或树上差分，可以处理树上路径的查询问题。

6. 时空复杂度分析

• 时间复杂度：每次操作O(log n)
• 空间复杂度：O(n log n)，因为每次修改只会创建O(log n)个新节点

7. 注意事项

1. 需要预先估算节点数量，一般开N * 40的空间
2. 注意版本号的存储和管理
3. 离散化可以减小值域，降低空间消耗
4. 合理设计节点信息，避免冗余存储

8. 总结

可持久化线段树是一种功能强大的数据结构，特别适合需要访问历史版本的场景。虽然实现相对复杂，但掌握了其核心思想和实现技巧后，能够解决许多传统数据结构难以处理的问题。