追溯数据结构

追溯结构允许修改过去的操作日志，并要求所有后续状态像历史原本如此发生一样被重算。它维护的不是若干冻结版本，而是一条操作依赖时间线；一次旧时刻编辑可能改变之后每个查询，所以可组合摘要与因果传播是核心成本来源。

队列例子 ​

原时间线在 $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更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。，没有完成追溯。

实现图像与证明责任 ​

通用朴素实现把时间线存成有序序列，每次追溯更新后重放后缀，若一次原 ADT 操作成本至多 $T$，一次历史编辑重放至多 $m$ 步，成本为 $O(mT)$，另计恢复起始状态及时间线维护；只有单位操作成本和相应的线性重放实例，才可简写为 $\mathrm{\Theta }(m)$。高效结构要利用 ADT 的可分解性，例如把一段操作摘要成可组合函数，再用平衡树维护组合。不能从“已有持久化版本”推断摘要可逆或历史编辑便宜。

能力边界 ​

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

可组合操作与难例 ​

一个明确可组合的版本固定幺半群理路幺半群Monoid具有双侧单位元的半群。 $(G,\cdot ,e)$，每条更新携带 $g$ 并执行 $s\leftarrow s\cdot g$。一段时间线的摘要就是按时间顺序的乘积；空段为 $e$。若元素占常数个字、乘法为常数时间，用搜索树增广理路搜索树增强定理与方法Search-tree augmentation区分可逐层重算的子树摘要与旋转后只需局部修复的中序聚合，并据此维护增强搜索树。在平衡时间树中维护中序乘积，历史插入、删除及任意前缀乘积都可在 $O(\log (m+2))$ 时间内完成；前缀状态是初态再乘该摘要。证明只使用结合律，合并次序不能倒置。

“状态属于某个群”本身不足以保证更新具有这种形式，任意状态变换仍须另行分析。队列与优先队列的过去删除可能改变后续被删元素，因此不能直接把它们的全部操作替换成上述固定乘数；它们可以有各自更专门的追溯算法。

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

时间编辑的执行轨迹 ​

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

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

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

完全追溯还要在任意时间切开前缀并返回当时答案。若整段操作没有已证明的定长摘要，或组合与查询解码不能在所需成本内完成，就不能直接套用这一高效区间聚合；这正是“操作日志可排序”与“追溯接口可高效实现”之间的鸿沟。