11 篇的线段树更新一个位置时，只修改从根到叶的一条路径。如果需要保留旧数组，复制整棵树会把一次更新的空间成本扩大到线性。路径复制保留未变子树，只为这条路径分配新节点，并把新根登记为一个版本。

这里的“持久化”指旧版本仍可访问。它不表示数据已经写入磁盘，也不提供崩溃恢复、事务提交或跨进程读取能力。

版本成为接口的一部分

输入是长度 n 的整数数组，初始化产生版本 0。沿用 11 篇的点增量和半开区间和，但每个操作都指定版本：

操作	输入与输出
`add(version,i,delta)`	从指定版本派生新版本，只把位置 i 增加 delta；返回新版本号
`sum(version,l,r)`	返回该版本 `[l,r)` 的整数和

版本号从 0 开始连续增加，不复用。任何已有版本都能作为更新起点，因此版本之间形成分叉关系，而不是只允许不断修改最新版本。非法版本、位置或区间抛出 IndexError；空区间返回 0。空数组可以建立版本 0，但没有合法更新位置。

规模变量除 n 外还包括成功更新次数 q。所有版本根都保留在 roots 中。调用者通过公开方法操作对象，不直接改写根表；节点使用不可变数据类表达只读共享约定。

只允许查询旧版本、更新最新版本，叫部分持久化。允许从任意旧版本派生，叫完全持久化。本实现属于后者，但没有合并两个版本的操作，也没有修改已经发生的历史操作。

哪些节点需要复制

以四个叶子为例，版本 0 的根为 R。更新左侧第一个元素，新根 R’ 的右子树仍指向旧节点 B；左子树必须建立 A’，目标叶也必须建立新节点。

版本 0: R  -> A  -> 旧叶0、叶1
           -> B  -> 叶2、叶3
版本 1: R' -> A' -> 新叶0、叶1
           -> B  -> 叶2、叶3

图中的叶1与 B 被两个版本共同引用。复制路径时先递归得到新孩子，未访问的另一个孩子直接保留引用，再用两者的和建立新父亲。

if index < mid:
    left = self._add(node.left, lo, mid, index, delta)
    right = node.right
else:
    left = node.left
    right = self._add(node.right, mid, hi, index, delta)
return self._node(left.total + right.total, left, right)

这段代码来自 examples/advanced-algorithms/persistent_sum.py。实现没有 12 篇的 lazy 标记；点更新只涉及一条路径。把可变 lazy 节点直接拿来共享，会让一次下推修改多个版本共同引用的孩子，破坏旧版本隔离。

为什么旧根仍表示旧数组

对更新区间长度作归纳。叶子处返回值增加 delta 的新节点，原节点不变。内部节点只递归更新包含目标位置的孩子，另一孩子未变；归纳假设保证递归结果只修改目标位置并保留旧子树。新父亲保存两个孩子之和，因此表示正确的新区间。

整个过程不写入任何旧节点。于是旧根可达的每个节点和指针均保持原值，旧根仍表示原数组。新根则表示恰有一个位置增加 delta 的数组。这同时证明了新版本正确性与旧版本隔离，不能只检查新版本总和就宣称两项都成立。

查询沿用 11 篇的区间分解：完整覆盖时返回节点总和，部分覆盖时递归相交孩子并相加。所有摘要属于同一个指定版本的根可达子图，查询既不修改节点，也不分配新树节点。

节点数与操作成本

本实现按中点划分区间，不补齐到二次幂。n 大于 0 时，有 n 个叶子，每个内部节点恰有两个孩子，因此初始节点数为 2n−1；空数组的根为 None，不分配节点。

目标叶深度为 d 时，每次更新恰好分配 d+1 个节点，包括叶子和根。即使 delta 为 0，也按相同路径复制，便于使用统一计数契约。中点划分使最大深度为 O(log(n+1))，所以树上的单点更新最坏时间和新增节点数均为 O(log(n+1))。连续区间查询每层只有常数条边界路径，同样具有最坏对数时间界。

根表使用 Python list，登记新根的追加操作是摊还常数成本，单次扩容可能复制已有根引用。因此完整 Python add 接口不能无条件宣称单次最坏对数时间；树路径复制是最坏对数，含根表追加的接口是摊还对数。这里没有随机选择，不涉及期望或高概率界。

保留 q 次更新后的空间为 O(n+q log(n+1)+q+1)，其中 q+1 明确计入根引用。这个式子按节点与引用个数计量，不是 Python 进程字节数。分析假设索引、加法和引用操作为单位成本；任意精度整数的位数增大时，应另计加法时间及数值存储空间。

版本分叉与有限检查

独立参照为每个版本保留普通 list 快照，每次更新复制指定快照。它虽然更新成本为 O(n)，但不依赖路径复制逻辑，适合校验有限输入。

1	`python3 examples/advanced-algorithms/check_persistent_sum.py`

本轮实际运行返回 passed：5832 个三步更新历史，以及 seed 20260919 的 300 次随机分叉更新。固定分叉例的四个版本总和为 [15,25,10,32]。检查同时覆盖旧版本查询不变、未更新子树引用共享、查询不分配节点，以及更新分配数等于目标路径节点数。

空数组、单元素、非二次幂长度与非法参数也有检查。这些结果属于教学实现的有限差分验证，不是一般正确性证明或本机性能测量；一般论证来自前面的结构归纳与路径计数。

一个直接反例是“只复制根，原地修改孩子”。更新后新根查询可能正确，但旧根仍指向同一个已被修改的孩子，历史值随之改变。只保留许多根指针并不自动获得持久化，共享节点不可变才是关键条件。

接口与验证边界

练习

对长度 5 的中点划分树，分别计算更新位置 0 和位置 4 的新增节点数。为什么不能要求每次更新都恰好分配同一个常数乘 log₂n？
从版本 0 分别更新两个不同位置，得到版本 1 与 2，再从版本 1 派生版本 3。列出每个版本数组，并说明版本 2 是否应包含版本 1 的更新。

参考资料

KIT/HPI 线段树课程讲义：PDF 第 149 页定义从任意版本查询与更新，第 150–158 页展示路径复制。本文的精确节点计数针对不补齐的中点划分实现。