02-可持久化线段树与版本差分.md 7.0 KB
可持久化线段树：版本、差分与路径第 k 小
本节目标
理解路径复制（path copying）为何让一次单点修改只新增 $O(\log V)$ 个节点；学会用两个前缀版本相减表示区间频次，并推广到树路径的四版本容斥。
前置知识与课前自测
前置：普通线段树、离散化、LCA。
- 单点修改会经过线段树多少节点？哪些子树可与旧版本共享？
- 版本
root[r]-root[l-1]的节点计数代表什么？ - 树路径 $u-v$ 的点权频次怎样由根到点前缀容斥？
答案
1. $O(\log V)$；只复制根到叶路径，未进入的另一儿子共享。 2. 数组位置 $[l,r]$ 内落入该值域节点的元素数。 3. `root[u]+root[v]-root[lca]-root[parent(lca)]`。问题动机与核心知识
持久化不是复制整棵树，而是把节点视为不可变对象。修改节点前创建副本，递归修改一个儿子，另一个儿子仍指向旧节点。若初始/空树节点编号为 0，一次插入新增一条值域路径。
第 $k$ 小查询在左右版本的左儿子计数差上决策：若左半元素数至少 $k$，进入左半；否则减去它并进入右半。这个过程同时完成选择与二分，不需要外层答案二分。
四版本容斥时把 count = countR(u)+countR(v)-countR(w)-countR(pw) 直接换成四个对应儿子的计数，其余逻辑与两根版本相同。
实现指南
- 节点池预估为
初始节点 + 修改次数 * (logV+1)，不足会越界。 - 版本根与原数组下标是两套编号，避免混用。
- 多个根做容斥时，每层必须对相同值域区间取对应儿子。
- 附件使用整数节点下标而非裸指针，便于容量检查和复制。
精选例题 1：K-th Number
来源与题意
- SPOJ-MKTHNUM K-th Number，Northeastern Europe 2004
- $n\le10^5,m\le5000$，数组元素互异；查询区间 $[l,r]$ 排序后的第 $k$ 个数。
Hint 1
版本 $i$ 保存前缀 $a[1..i]$ 的值域频次。Hint 2
区间频次是版本 $r$ 减版本 $l-1$。Observations
- 询问区间很多但数组静态，前缀版本可复用所有查询。
- 值域只关心顺序，先离散化；叶子秩最后映回原值。
- 第 $k$ 小只需计数，不需在每个节点保存具体元素。
Editorial 与正确性证明
依次从前一版本插入 $a_i$ 得到 root[i]。查询时，当前值域左半的区间元素数由两个根左儿子计数相减得到。若不少于 $k$，答案必在左半；否则左半全部排在答案前，转右半并令 $k$ 减该数。区间每次减半，抵达叶子时其秩唯一。
预处理 $O(n\log n)$，每问 $O(\log n)$，节点 $O(n\log n)$。
核心伪代码与附件
root[0] = empty_value_tree
for i in 1..n: root[i] = insert_copy(root[i-1], rank(a[i]))
kth(left_root, right_root, k, value_interval):
left_count = count(right_root.left) - count(left_root.left)
if k <= left_count: recurse on both left children
else: recurse on both right children with k -= left_count
kth4(u, v, w, pw, k, value_interval):
left_count = count(u.left)+count(v.left)-count(w.left)-count(pw.left)
if k <= left_count: recurse on (u.left, v.left, w.left, pw.left)
else: recurse on right children with k -= left_count
精选例题 2：Count on a tree
来源与题意
- SPOJ-COT Count on a tree
- $N,M\le10^5$；点带权，询问树路径 $u-v$ 上第 $k$ 小权值。
Hint 1
每点版本保存从整棵树根到该点的权值频次。Hint 2
设 $w=LCA(u,v)$，路径频次做四版本容斥。Observations
- 数组的“前缀”被树上的“根路径”替代，持久化结构没有改变。
root[u]+root[v]-2*root[w]会把 LCA 权值也删掉，必须改成减root[w]与root[parent(w)]。- 正确性依赖每点版本从父版本只插入自身一次。
Editorial 与证明
任意值域区间内，根到 $u$ 与根到 $v$ 的计数相加，公共前缀根到 LCA 被算两次。减去根到 LCA 与根到 LCA 父亲，恰保留路径并让 LCA 计一次。把第 k 小的左右计数公式替换为四根容斥即可；LCA 用倍增预处理。
预处理 $O(n\log n)$，每问 LCA 与选择均 $O(\log n)$，空间 $O(n\log n)$。
核心伪代码与附件
DFS/BFS from tree root:
version[v] = insert_copy(version[parent[v]], rank(weight[v]))
w = LCA(u, v)
pw = parent(w), or empty version when w is root
kth4(version[u], version[v], version[w], version[pw], k, value_interval)
精选例题 3：Range Queries and Copies
来源与题意
- CSES-1737 Range Queries and Copies
- $n,q\le2\times10^5$；维护多个数组版本，支持修改某版本单点、查询某版本区间和、复制版本。
Hint 1
每个数组只保存一个根。Hint 2
复制版本只复制根编号；修改时路径复制，不改变共享旧节点。Observations
- “修改版本 k”会更新该版本根，但之前由它复制出的版本必须保持不变。
- 根编号复制为 $O(1)$，真正空间只在后续修改时产生。
- 查询是纯读操作，不应 push 或创建节点。
Editorial 与正确性证明
初始数组建立普通和树。单点赋值沿路径复制，重新计算新节点和；不在路径上的节点共享且值未变。复制操作追加同一个根编号。由节点不可变性，任何旧根可达的节点内容永不被修改，所以所有历史/分支版本语义保持；新根恰反映指定单点更新。
建树 $O(n)$，修改/查询 $O(\log n)$，复制 $O(1)$，空间 $O(n+q\log n)$。
核心伪代码与附件
roots = [build(initial_array)]
set(version, position, value): roots[version] = update_copy(roots[version], position, value)
sum(version, l, r): query(roots[version], l, r)
copy(version): roots.append(roots[version])
扩展与联系
主席树是“可持久化权值线段树”的常见竞赛称呼，不等于所有持久化线段树。若修改是区间 Lazy，路径复制还要连同标记语义一起保持不可变，复杂度与实现风险更高。
总结与自检
- 为什么一次更新只新增对数节点？
- 两前缀根相减如何得到区间频次？
- 树路径为何是四根而不是三根？
- 版本复制后修改原版本，副本为何不变？
课后训练建议
先把节点池缩小到故意溢出，学会估算容量；用朴素排序/数组副本对拍三题。路径题重点打印 LCA 为端点、LCA 为根、u=v 三种容斥结果。