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