可持久化线段树（Persistent Segment Tree）详解
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. 注意事项
- 需要预先估算节点数量，一般开
N * 40的空间 - 注意版本号的存储和管理
- 离散化可以减小值域，降低空间消耗
- 合理设计节点信息，避免冗余存储
8. 总结
可持久化线段树是一种功能强大的数据结构，特别适合需要访问历史版本的场景。虽然实现相对复杂，但掌握了其核心思想和实现技巧后，能够解决许多传统数据结构难以处理的问题。