追溯数据结构

时间线模型 ​

设 ADT 的更新按全序时间戳组成序列 $\mathcal{T}=(u_1,\dots ,u_m)$，从初态依次执行得到每个时刻的逻辑状态。追溯更新 insertUpdate$(t,u)$ 或 deleteUpdate$(t)$ 改写 $\mathcal{T}$，正确性要求所有较晚时刻都等价于在新时间线上从头执行。复杂度必须同时写历史长度 $m$、追溯更新时间和查询时间。

部分追溯允许在任意过去修改更新，但只查询当前末端状态；完全追溯还允许 query$(t)$ 读取任意时刻。时间戳冲突需用稳定二元键或明确先后规则处理。

队列例子 ​

原时间线在 $t=2$ 执行 enqueue$(A)$，$t=7$ 执行 dequeue。若在 $t=5$ 插入 enqueue$(B)$，则 $t=6$ 的队列从 $[A]$ 变为 $[A,B]$，而 $t=8$ 从空队列变为 $[B]$。修改的是过去操作，后果传播到未来；仅保存并读取修改前的 $t=5$ 版本属于持久化公理库持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。，没有完成追溯。

实现图像与证明责任 ​

通用朴素实现把时间线存成有序序列，每次追溯更新后重放后缀，更新可达 $\mathrm{\Theta }(m)$。高效结构要利用 ADT 的可分解性，例如把一段操作摘要成可组合函数，再用平衡树维护组合。不能从“已有持久化版本”推断摘要可逆或历史编辑便宜。

能力边界 ​

rollback 只按栈顺序撤销最近修改；partial/full persistence 决定从哪些版本查询和分叉；retroactivity 决定能否改写过去的操作。四者没有简单的同成本包含关系。完全追溯还可能比部分追溯严格更难；必须单独报告 query$(t)$，而不是只写一个含糊的“操作复杂度”。

可组合操作与难例 ​

若 ADT 状态是群元素，时间段摘要可取操作乘积，插入过去操作只需在平衡树叶修改并向根重算，得到 $O(\log m)$ 更新与前缀查询。队列、优先队列等状态不由常数大小群摘要决定：一次过去的 dequeue 会改变之后究竟删除哪个元素，影响可沿整条历史传播。

因此复杂度来自操作语义，而非时间线容器本身。历史树能在 $O(\log m)$ 找到时间戳，并不表示 ADT 状态也能同成本修复；正确性证明需给出节点摘要的组合律和从根摘要恢复查询答案的方法。

时间编辑的执行轨迹 ​

考虑时间线 enqueue(a)@1, enqueue(b)@4, dequeue()@7。在时刻 3 插入 dequeue()@3 后，原来时刻 7 返回的元素会从 a 改为 b；这说明修改历史不能只修补时刻 3 的快照，而要重新建立其后的因果关系。

部分追溯结构只允许询问“现在”的状态：

1. 按时间键把操作放入可分裂、可合并的搜索树；
2. 每个子树保存该段操作对抽象状态的可组合摘要；
3. 插入或删除历史操作后，只沿搜索路径重算摘要；
4. 根摘要给出当前状态，却不一定支持任意过去时刻查询。

完全追溯还要在任意时间切开前缀并返回当时答案。若操作摘要不是结合的有限对象，例如队列中一次删除会改变后续大量返回值，就不能直接套用区间聚合；这正是“操作日志可排序”与“追溯接口可高效实现”之间的鸿沟。

参考资料

• Erik Demaine, John Iacono, Stefan Langerman, Retroactive Data Structures, ACM Transactions on Algorithms, 2007.
• James Driscoll et al., Making Data Structures Persistent, JCSS, 1989.