# 可持久化线段树：版本、差分与路径第 k 小

## 本节目标

理解路径复制（path copying）为何让一次单点修改只新增 $O(\log V)$ 个节点；学会用两个前缀版本相减表示区间频次，并推广到树路径的四版本容斥。

## 前置知识与课前自测

前置：普通线段树、离散化、LCA。

1. 单点修改会经过线段树多少节点？哪些子树可与旧版本共享？
2. 版本 `root[r]-root[l-1]` 的节点计数代表什么？
3. 树路径 $u-v$ 的点权频次怎样由根到点前缀容斥？

<details><summary>答案</summary>

1. $O(\log V)$；只复制根到叶路径，未进入的另一儿子共享。
2. 数组位置 $[l,r]$ 内落入该值域节点的元素数。
3. `root[u]+root[v]-root[lca]-root[parent(lca)]`。

</details>

## 问题动机与核心知识

持久化不是复制整棵树，而是把节点视为不可变对象。修改节点前创建副本，递归修改一个儿子，另一个儿子仍指向旧节点。若初始/空树节点编号为 0，一次插入新增一条值域路径。

第 $k$ 小查询在左右版本的左儿子计数差上决策：若左半元素数至少 $k$，进入左半；否则减去它并进入右半。这个过程同时完成选择与二分，不需要外层答案二分。

四版本容斥时把 `count = countR(u)+countR(v)-countR(w)-countR(pw)` 直接换成四个对应儿子的计数，其余逻辑与两根版本相同。

## 实现指南

- 节点池预估为 `初始节点 + 修改次数 * (logV+1)`，不足会越界。
- 版本根与原数组下标是两套编号，避免混用。
- 多个根做容斥时，每层必须对相同值域区间取对应儿子。
- 附件使用整数节点下标而非裸指针，便于容量检查和复制。

## 精选例题 1：K-th Number

### 来源与题意

- [SPOJ-MKTHNUM K-th Number](https://vjudge.net/problem/SPOJ-MKTHNUM)，Northeastern Europe 2004
- $n\le10^5,m\le5000$，数组元素互异；查询区间 $[l,r]$ 排序后的第 $k$ 个数。

<details><summary>Hint 1</summary>版本 $i$ 保存前缀 $a[1..i]$ 的值域频次。</details>
<details><summary>Hint 2</summary>区间频次是版本 $r$ 减版本 $l-1$。</details>

### Observations

- 询问区间很多但数组静态，前缀版本可复用所有查询。
- 值域只关心顺序，先离散化；叶子秩最后映回原值。
- 第 $k$ 小只需计数，不需在每个节点保存具体元素。

### Editorial 与正确性证明

依次从前一版本插入 $a_i$ 得到 `root[i]`。查询时，当前值域左半的区间元素数由两个根左儿子计数相减得到。若不少于 $k$，答案必在左半；否则左半全部排在答案前，转右半并令 $k$ 减该数。区间每次减半，抵达叶子时其秩唯一。

预处理 $O(n\log n)$，每问 $O(\log n)$，节点 $O(n\log n)$。

### 核心伪代码与附件

```text
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
```

[完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/SPOJ-MKTHNUM.cpp)

## 精选例题 2：Count on a tree

### 来源与题意

- [SPOJ-COT Count on a tree](https://vjudge.net/problem/SPOJ-COT)
- $N,M\le10^5$；点带权，询问树路径 $u-v$ 上第 $k$ 小权值。

<details><summary>Hint 1</summary>每点版本保存从整棵树根到该点的权值频次。</details>
<details><summary>Hint 2</summary>设 $w=LCA(u,v)$，路径频次做四版本容斥。</details>

### 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)$。

### 核心伪代码与附件

```text
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)
```

[完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/SPOJ-COT.cpp)

## 精选例题 3：Range Queries and Copies

### 来源与题意

- [CSES-1737 Range Queries and Copies](https://vjudge.net/problem/CSES-1737)
- $n,q\le2\times10^5$；维护多个数组版本，支持修改某版本单点、查询某版本区间和、复制版本。

<details><summary>Hint 1</summary>每个数组只保存一个根。</details>
<details><summary>Hint 2</summary>复制版本只复制根编号；修改时路径复制，不改变共享旧节点。</details>

### Observations

- “修改版本 k”会更新该版本根，但之前由它复制出的版本必须保持不变。
- 根编号复制为 $O(1)$，真正空间只在后续修改时产生。
- 查询是纯读操作，不应 push 或创建节点。

### Editorial 与正确性证明

初始数组建立普通和树。单点赋值沿路径复制，重新计算新节点和；不在路径上的节点共享且值未变。复制操作追加同一个根编号。由节点不可变性，任何旧根可达的节点内容永不被修改，所以所有历史/分支版本语义保持；新根恰反映指定单点更新。

建树 $O(n)$，修改/查询 $O(\log n)$，复制 $O(1)$，空间 $O(n+q\log n)$。

### 核心伪代码与附件

```text
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])
```

[完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/CSES-1737.cpp)

## 扩展与联系

主席树是“可持久化权值线段树”的常见竞赛称呼，不等于所有持久化线段树。若修改是区间 Lazy，路径复制还要连同标记语义一起保持不可变，复杂度与实现风险更高。

## 总结与自检

1. 为什么一次更新只新增对数节点？
2. 两前缀根相减如何得到区间频次？
3. 树路径为何是四根而不是三根？
4. 版本复制后修改原版本，副本为何不变？

## 课后训练建议

先把节点池缩小到故意溢出，学会估算容量；用朴素排序/数组副本对拍三题。路径题重点打印 LCA 为端点、LCA 为根、u=v 三种容斥结果。