path copying · partial / full / confluent

路径复制与持久化的分级

一个数据结构的每次修改都产出一个新版本，而全部旧版本仍可正常查询，就说它是 persistent 的。这个性质在两个方向上有用：编辑器的 undo 栈、版本控制、时间旅行调试要的是「回到过去」；函数式语言里的不可变值要的是「别人拿到的引用不会在脚下变化」。两者要的是同一件事。

朴素实现只有一句：每次修改前先整个复制一份。这当然正确，代价也当然是 $O(n)$ 。10 万元素的数组做 1 万次「改一格并留档」，光是格子写入就有 $10^9$ 次，按每格 8 字节算 7.6 GB。本页要说的是怎样把这笔账压到 $O(\log n)$ 。

1 · 持久化的分级

版本之间的派生关系构成一张有向图：一条边表示「由某个版本经一次操作得到另一个版本」。允许什么样的边，就决定了是哪一级持久化。

定义 1.1（persistence 的三个级别） 设 $V$ 为版本集合。

partial persistence：任意版本可查询，但只有最新版本可被修改。版本图是一条链。
full persistence：任意版本可查询，也可被修改并派生出自己的后继。版本图是一棵树。
confluent persistence：在 full 的基础上再允许「一次操作读两个版本、产出第三个」。版本图是 DAG。

三级的实用性递增，实现难度也递增。Driscoll 等人 1989 年的论文 [1] 同时给出了两条通用路线。一条是 fat node：不复制节点，而是在每个字段上挂一张「修改时间戳到值」的表，查询时按版本号二分。它的空间是每次修改 $O(1)$ ，代价是每次读多一个 $O(\log m)$ 的因子（ $m$ 为版本数）。另一条就是本页的主角，它反过来：读没有任何额外代价，写多花 $O(\log n)$ 空间。

confluent 一级要单列出来，是因为它会让 path copying 的空间分析失效。full persistence 下每个版本至多有一个父版本，总空间是「修改次数乘以路径长」；confluent 下一个版本可以被引用任意多次，Fiat 与 Kaplan [2] 给出的例子里， $m$ 次合并操作能把逻辑上的结构撑到 $2^m$ 大。真实实现只能靠「合并的两边高度重叠」这一经验事实活着，而不是靠上界。

2 · 路径复制

线段树是把这件事讲清楚的最小载体：它是完全二叉树，第 $i$ 个叶子存 $a[i]$ ，内部节点存子树的聚合值。普通线段树的单点修改是「走到叶子、改值、回溯刷新沿途的聚合」，一共触碰 $\lceil \log_2 n \rceil + 1$ 个节点。

path copying 把「触碰」换成「新建」：不改原节点，而是给这条路径上的每个节点造一个副本，副本的一个孩子指向新造的下层副本，另一个孩子直接指向旧树里原来那个兄弟子树。递归结束时得到一个新的根，旧根一个字节也没动。

图 2-1 · 一次单点修改之后的整棵新树，蓝色实心是本次新建的节点，灰色是与旧版本共用同一个对象的节点。可调 n 与被改的下标，也可关掉共享节点只看那条路径。

判断共享是否真的发生了，判据只能是对象同一性而不是内容相等。引擎里的 shareStat 把两个版本可达的节点各收进一个 Set，数交集大小；测试则更进一步，在 update 前后各给旧根拍一次快照，逐个节点比对 id 与聚合值。节点本身走 Object.freeze，任何试图就地改的写法会在 ES module 的严格模式下抛 TypeError，不至于悄悄溜过测试。

3 · 共享量的账

新建量恒等于树高，与 $n$ 无关地只增长到对数级；共享量则是余下的全部。

$n$	单版本节点数 $2n-1$	一次修改新建	共享	共享率
8	15	4	11	73.33%
64	127	7	120	94.49%
1024	2047	11	2036	99.46%
65536	131071	17	131054	99.99%
1000000	1999999	21	1999978	99.999%

小 $n$ 下路径复制并不划算： $n = 8$ 时新建 4 个节点、共享 11 个，比起直接复制 8 个格子的数组，省下的那点空间还抵不过指针本身的开销。转折点在几百这个量级。

把规模拉到有意义的地方：长度 1024 的数组、1000 次随机单点修改、全部 1001 个版本都留着。实际活着的节点是 13047 个，等于初始的 2047 加上 1000 次修改各 11 个。同样 1001 个版本若各存一棵完整的树，需要 2049047 个节点，是前者的 157 倍。

警示 · 「 $O(\log n)$ 空间」说的是每次修改的增量，不是总量。留住 $m$ 个版本要 $O(n + m \log n)$ ， $m$ 一大仍然可观。真正省下的是「与 $n$ 成正比的那一项只付一次」；如果版本数远大于结构规模，path copying 的优势就退回到常数。

4 · 版本图与合并

full persistence 在 path copying 下是免费的：updateSeg 的入参是一个根指针，传哪个版本的根都一样能跑。真正需要额外写代码的只有 confluent 一级，因为它要定义「两个版本怎么合成一个」。

引擎里实现的是逐格取较大值，写法是同时下降两棵树，遇到同一个对象就整段返回、不再下探。这个提前返回是全部收益的来源：两个版本共享的子树在合并时被原样复用。

图 4-1 · 可从任意旧版本派生新版本，也可把两个版本逐格取大合成第三个。可单击版本切换派生的父版本，观察表格里每个版本的新建节点数与总节点数的比值。

合并的代价有一处实测修正了原先的估算。合并两个相隔 100 步修改的版本，两者最多有 100 个叶子不同，按「差异叶子数乘树高」估应新建 $100 \times 13 = 1300$ 个节点（ $n = 4096$ ，树高 13）。实测是 651 个，正好约一半。原因是 100 条根到叶子的路径在树的上层大量重合，重合段只重建一次；越靠近根重合越严重，第一层永远只有一个节点。所以 confluent 合并的真实代价是「差异叶子集合的 Steiner 树大小」，而不是路径长度的简单相加。作为对照，两个各只改一处的版本合并只新建 13 个节点，而全量重建整棵树要 8191 个。

5 · 参考文献

Driscoll, J. R., Sarnak, N., Sleator, D. D., & Tarjan, R. E. (1989). Making data structures persistent. Journal of Computer and System Sciences, 38(1), 86–124.
Fiat, A., & Kaplan, H. (2003). Making data structures confluently persistent. Journal of Algorithms, 48(1), 16–58.
Demaine, E. (2012). Persistent data structures. MIT 6.851 Advanced Data Structures, Lecture 1.
Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press.
线段树本身的建法与区间查询见区间查询与区间修改；平衡树上的同一套手法见树 · 遍历、平衡 BST 与前缀 / 度量树。