第14篇用版本根保留旧状态。对旧版本发起查询，得到的答案不会因为新版本产生而改变。追溯数据结构允许编辑过去的操作序列，之后的历史查询则按照编辑后的序列重新解释。两个接口都出现时间参数，但承诺保留的东西不同。

本篇只实现整数增量事件：在指定时间插入一个加法，或删掉已有事件，再查询某时刻之前的累计和。这个有界操作集可以用排序数组与前缀和实现，足以验证语义，不需要先实现一个通用追溯框架。

两种时间不能混用

把一次编辑请求的提交次序记为版本编号v，把事件在被建模历史中的位置记为时间t。提交顺序可以是先录入t=10，再录入t=2。版本编号仍向前增长，逻辑时间却不要求按输入顺序排列。

持久化保留v所指的旧状态；完全持久化允许从旧版本分支产生新版本，原分支仍存在。追溯编辑把t=2处的事件放入当前解释的历史，此后查询t=3就必须计入这个事件。若还要求查看“编辑之前看到的历史”，需要额外保存编辑版本，本实现没有这个接口。

需求 被查询的对象 新编辑对旧查询的影响
持久化查询版本v 固定版本状态 相同v的答案不变
追溯查询逻辑时间t 当前事件序列在t前的状态 编辑早于t的事件可能改变答案

Demaine等人的论文把只支持查询当前状态称为部分追溯，允许查询任意历史时刻称为完全追溯。这里的“完全”修饰查询时间范围，不表示支持任意类型的操作。

增量事件的输入输出

RetroactiveSum初始为空。timestamp和delta按Python整数契约使用，允许负时间、负增量与零增量，不负责解析外部文本。每个时间戳至多一个事件；若需要同一时刻多个事件，应先另定顺序规则，不能依赖字典或容器的偶然顺序。

insert(t,d)添加时间t的增量d，重复时间抛ValueError；delete(t)删除时间t的事件，不存在则抛KeyError。两种拒绝均不改变已有历史。

query(t)返回所有事件时间严格小于t的delta总和，沿用系列半开区间端点约定。total()返回当前保留事件的总和。空历史的两种查询都返回0。总和没有余额非负、容量上限或业务合法性限制。

这里的delete是编辑器删除一条历史记录，不是向历史追加“删除某个对象”的操作。事件本身只有整数加法，所以删去任意事件后，其他事件仍然有定义。若事件包括出队，删掉过去的入队可能使后来出队非法，需要另设一致性条件。

排序数组与前缀和

实现保存同长数组times和deltas，times严格递增。prefix长度比它们多1，prefix[0]=0，prefix[j]是前j个delta之和。

插入用bisect_left找到位置，先检查重复，再在两数组同一位置插入并重建prefix。删除先查找与检查存在性，移除对应两项后重建。没有偷偷保留原prefix；编辑早期事件可能改变所有后续前缀。

查询令j=bisect_left(times,t)，返回prefix[j]。二分边界左侧恰是所有时间小于t的事件，不包括时间等于t的事件。例如事件(1,+5)、(3,+2)给出query(1)=0、query(2)=5、query(3)=5、query(4)=7。

正确性分成两个不变量。插入或删除保持times严格递增，并保持时间与增量一一对应。重建从prefix[0]=0开始，每一步加上下一事件增量，归纳得到每个prefix[j]的定义。二分再把查询条件转换成前缀长度，所返回的和就是接口要求的结果。

为什么当前补偿不能改写历史

从事件(1,+5)、(3,+2)开始，两份结构分别执行delete(1)和insert(10,−5)。两者total都变成2；前者query(2)=0，后者query(2)=5。

这个反例说明，当前总和相等并不能证明历史语义相同。在未来追加反向增量，只抵消最终总和；过去时刻的前缀根本不包含这条补偿。独立检查同时比较total与多个query端点，避免只测当前值而漏掉差别。

加法的可交换性使总和不依赖事件排列，逆元使删除贡献容易抵消，但历史查询还要判断事件位于端点哪一侧。因此只维护一个总和变量能够支持本例的当前查询，却不能直接给出完全追溯查询。

操作换成赋值时，甚至最终值都不能靠“相反操作”一般地恢复。先赋值5再赋值2，删除第一次赋值后结果仍为2；把5减掉却得到−3。可逆增量的规则不能直接推广到覆盖写入。

成本与fat node的不同职责

记当前事件数为q。二分需要最坏O(1+log(q+1))次比较；数组插入、删除与前缀重建需要O(q+1)次基本操作。更新的保守最坏界为O(q+1)，query为O(1+log(q+1))，total为O(1)，保存O(q+1)个整数或引用。重建中的列表追加按数组摊还规则累计为线性，不会把整个更新降低为常数摊还成本。

这些是确定性的操作次数界，不依赖随机输入，既不是期望界也不是高概率界。时间戳和总和可能是大整数；若相关整数最多L位，应另计整数比较、加法和对象存储的位成本，不能把任意大的Python整数当作单个机器字。

fat node解决的是另一种存档方式：节点字段保留按版本标记的修改记录，读取某版本时定位该版本对应的字段值。在线性版本序列上，可以按版本号找不晚于目标版本的最近修改。完全持久化的分支版本还需要祖先关系，不能仅按整数编号找前驱。

给字段增加修改日志，并没有说明如何把旧事件的改变传播到所有后续派生状态。前者可以用来实现持久化，后者仍须分析具体操作之间的依赖。本篇数组重建正是对加法事件依赖的一种直接处理，更新代价也明确支付了线性扫描。

复跑与证据范围

从仓库根目录运行：

1
python3 examples/advanced-algorithms/check_retroactive_sum.py

本次运行退出码为0：枚举长度不超过3的1885个短操作历史，并执行500次固定种子随机编辑，累计94428次历史查询与独立字典遍历求和对照；1965次非法操作被拒绝。删除旧事件与当前补偿的反例也输出到结果中。

参照不使用待测prefix或二分定位，而是遍历字典逐个判断time<t。结果保存在writing-plans/advanced-algorithms/evidence/retroactive-sum-results.json。这证明这些输入上的实现与参照一致；任意操作序列的正确性依据仍是前面的不变量证明。

练习

  1. 依次插入(4,+3)、(1,−2)、(3,+5)，列出query(1)、query(3)、query(4)、query(5)。删除时间3的事件后，哪些答案改变？
  2. 增加“按提交版本查询编辑前历史”的需求。说明现有三个数组缺少什么信息，并解释逻辑时间t为什么不能直接充当持久化版本号v。

参考资料