浅谈可追溯化数据结构

我们都见到过很多有关“可撤销数据结构”、“可持久化数据结构”……等等这样一类的 DS 问题。

事实上，存在这样一类数据结构，它的作用听起来和可持久化数据结构很像，它在 OI 中的出现次数也相比可持久化数据结构较少……但是它就是这篇博客的研究对象——可追溯化数据结构。

定义

通常情况下，可追溯化数据结构应当支持形如下面形式的操作：

在时刻 $t$ 对数据结构进行一次修改。
删除某次修改。
在时刻 $t$ 对数据结构进行一次数据查询。

或者，更为直观地，可追溯化数据结构不仅要维护数据结构当下的数值，还要维护整条时间线。支持“穿越”回某个时间点，撤销曾经做下的修改操作。和直接按树形回溯不同，需要注意的是，在某个时间点删除了这个时间点的操作，这个时间点之后的操作不会被一并撤销，而是会保留。

特别地，有一类特殊的可追溯化的要求：操作三满足 $t=\infty$ 。这样的数据结构为部分可追溯化（Partial Retroactivity，PR）的；否则（ $t$ 可以取任意数）为完全可追溯化（Full Retroactivity，FR）的。

当然还有一类特殊的分类，因为难度较大，我们将会在本文的结尾作为『尾杀』放出。

一些 DS 的可追溯化

并查集

并查集的可追溯化是比较容易的。

优先考虑 PR 问题，可以注意到，加边操作是具有交换律的（交换两次加边操作不影响最终答案）。因此 PR 并查集就是动态图连通性问题（支持添加/删除一条边，查询两点连通性）。

对于 FR 路径，考虑离线操作。对每条边记录权值表示其删除时间。两点连通当且仅当两点间存在一条路径，使得路径上所有边都没有被删除。LCT 维护最大生成树即可。

栈

PR 栈和 FR 栈其实差不多，这里只考虑 FR 栈。

不难发现当我需要查寻 $t$ 时刻的栈顶时，相当于找到一个 $t$ 时刻以前的某个插入操作，满足它后面的插入和删除操作数量相同（即后面加的刚好被删完）。

将插入操作视为权值 $1$ ，删除操作视为 $-1$ 。则查询结果相当于寻找最后一个满足后缀和（不包括自身）为 $0$ 的插入操作所插入的数字。

用平衡树维护操作序列，由于每个数都是 $\pm1$ ，因此任意区间的后缀和一定都是一段连续的值。查找这个后缀和为 $0$ 的点是可以在平衡树上二分的。复杂度为单个 $\log$ 。

队列

这个 PR 版本和 FR 版本有一定区别。优先考虑 PR 队列。

显然，先依次执行完所有插入操作，再依次执行完所有的删除操作，最终结果不变。

于是问题的等价于要求在某一位置插入或删除一个元素，寻找某个位置的值。过程中动态维护当前的队头队尾在数组上对应的下标即可。平衡树可以做到单 $\log$ 。

进一步考虑，分析插入和删除操作对指针位置产生的影响，不难发现每次操作这两个指针都只会移动到相邻的格子上。因此这里的“随机访问”并不是真正的随机访问，我们只需要一个链表支持插入、删除，维护查询结果的指针左右移。单次操作 $\mathcal O(1)$ 。

进一步考虑 FR 队列。

显然不能先把所有插入做完再把所有删除做完了。但是插入操作和删除操作依然是相互独立的。用两个平衡树 $T_i,T_d$ 分别维护插入操作和删除操作的操作序列。对于修改某个时间点的操作，直接到对应平衡树上修就可以了。下面考虑查询操作：

查询队尾时，在 $T_i$ 里找到最后一次插入操作即可。
查询队头时，在 $T_d$ 里先找到这个时间之前有多少个删除操作（假设为 $k$ 个），在 $T_i$ 平衡树上二分找到下一个（第 $k+1$ 次插入）插入操作即可。

每次操作的复杂度为单 $\log$ 。

双端队列

考虑栈和队列的综合：维护一个可追溯化的、允许随机访问的双端队列。这里 PR 双端队列和 FR 双端队列还是差不多的，只考虑 FR 双端队列。

类似队列的做法，可以得到答案一定来自于某个左插入或一次右插入。如果能分别求出左插入里最可能是答案的数和右插入里最有可能是答案的数，知道如何区分就做出来了。

考虑手写双端队列的过程，插入时 a[--L]=x 或 a[++R]=x；删除时 ++L 或 --R。如果能求出每次查询时 $L$ 的位置， $a$ 数组，以及队列的大小，就能很容易维护这些操作。

开两个平衡树 $T_l,T_r$ 表示维护与左侧/右侧有关的操作。用栈类似的方式，将插入和删除赋 $\pm1$ 的权值。对于一个时刻 $t$ 上的查询，其对应的答案所在下标 $i$ 也可以在平衡树上维护前缀和求出。

而 $a_i$ 的值一定是最后一次左插入后 $L=i$ 的数或右插入后 $R=i$ 的数。在平衡树上根据后缀和二分，取二者中较晚的值为答案即可。每次操作的复杂度为单 $\log$ 。

非显性可追溯化与优先队列

~~正片开始。~~

在接触非显性可追溯化之前，应该要先推出如何维护 PR,FR 优先队列。因为非显性可追溯化是比 PR,FR 困难一些的。

PR,FR 优先队列

前面都在维护一堆一堆的下标。这次来一个真的和值有点关系的东西。不妨假设现在要维护小根堆。

考虑 PR 优先队列，做出一个 key-time 图像：

坐标 $(x,y)$ 的每个点代表在时间 $y$ 插入了一个值为 $x$ 的数。横向箭头形式化地体现了这个值在优先队列中存在的时间段。竖向箭头表示在这个时间进行了一次弹出最小值操作。

可以直观地理解为一条竖线会不断往上，直到与一条横线碰撞，然后这两条线的后面部分就都被截断了。形成一个个倒着的 L。

单独维护这个图像仍然是困难的，因为一次操作可能会产生一系列连锁反应，使得后面很多条竖线碰撞的横线改变。因此我们应当维护变化量不大的量。注意到在 PR 队列下，我们不关心这个队列的变化过程，可以只关心最终的结果。也就是队列最终的元素集合 $Q$ 。显然每次操作 $\Delta\left|Q\right|\leq 1$ 。

回到原图，定义一个时刻是关键的，当且仅当在这个时刻的队列元素集合满足 $q_t\subseteq Q$ 。例如下图中，绿色线条表示的时刻就是关键的：

考虑在时刻 $t$ 插入数字 $x$ 对最终队列 $Q$ 带来的影响。相当于插入了 $\max(x,\max\{x'| \text{delete-time}_{x'}\geq t\})$ 。设 $t'$ 为 $t$ 时刻前的第一个关键时刻，则相当于插入了 $\max\{x\notin Q | \text{delete-time}_x \geq t'\}$ 。类似地，删除一个最小值的操作也可以用类似的方式表述。

开一个 $T_1$ 维护操作序列，每个操作加上一个权值：对于插入操作，若 $x\in Q$ 为 $0$ ，否则为 $1$ ；对于删除操作，赋 $-1$ 。可以得到关键时刻满足这个时刻对应的前缀和为 $0$ 。求关键时刻就可以在平衡树上二分了。

对于求出符合时间范围的数字，可以再开一个平衡树 $T_2$ ，仅维护插入操作。对于每个不在 $Q$ 内的点，维护它们的最大值；对于每个在 $Q$ 内的点，维护它们的最小值（如果你不嫌烦，开两个平衡树分别维护 $\max\{x|x\notin Q\}$ 和 $\min\{x|x\in Q\}$ 也是没有问题的）。

每次操作就可以用 $T_1,T_2$ 求出 $Q$ 如何改变，更新 $Q$ 后然后再反过来更新 $T_1,T_2$ 即可。复杂度单 $\log$ 。常数懂的都懂。

对于 FR 优先队列？

显然存在一种方案：操作分块。对操作分块后，每个块端点和其前缀用 PR 的方法做。时间复杂度为 $\sqrt n T(n)$ ，其中 $T$ 表示 PR 做法的复杂度。

当然了，这个做法没有什么前途，下面分析一个 poly-log 的做法。

仍然考虑用平衡树维护操作序列，不过我们扩充成树套树，将每个点的子树对应的区间再用一个平衡树维护这个区间在 PR 情况下的答案，还要一个平衡树维护删除的元素构成的集合。

记一个区间上开的这两个平衡树为 $(T_1,T_2)$ ，一次询问相当于合并至多 $\log n$ 个二元组 $(T_1,T_2)$ 。合并是很难用 log 做法实现的，考虑更朴素的方式：将答案用若干个二元组的并来表示。

设 $(S_1,S_2)$ 和 $(T_1,T_2)$ 每个集合（平衡树）分别用了 $k$ 个集合表示。二分找到 $S_1\cup T_2$ 中第 $\left|S_1\right|$ 大的元素，以此将 $S_2,T_2$ 对应的 $k$ 个集合划分成 $2k$ 个集合。即可得到集合并用 $3k$ 个集合表示的结果。

一次合并的复杂度为 $k\log n$ 。按分治的方式合并，一共会分治 $\log \log n$ 层。自下而上合并所有集合的个数和为 $(\frac{3}{2})^in$ 。可以计算出单次操作复杂度 $\log^2 n$ ，查询复杂度 $\log^3 n$ 。

非显性可追溯化

非显性可追溯化（Nonoblivious Retroactivity，NR）要求查询一次修改操作会产生的错误（即询问的结果发生了改变的询问）发生在哪里。

举个例子，维护一个优先队列：

非显性可追溯化优先队列

在 $t$ 时刻将 $x$ 插入。
在 $t$ 时刻弹出队列最小值。
撤销某个插入操作或弹队操作。
在 $t$ 时刻查询队列中元素的最小值。

每次修改操作（1,2,3 共三类）完成后，查询答案发生改变的询问的编号。如有多个输出询问时间最早的。

key-value 图像总是有用的。这一次把竖向箭头的含义从删除最小值改成查寻最小值，至于删除最小值操作，不再用箭头表示：

对于一次修改操作，可能会产生如下两种『错误』：

定义因插入插入和删除删除产生的错误为交叉错误（上图右下的例子），因插入删除和删除插入产生的错误为浮动错误（上图上方的例子）。对两种错误分别维护。

对于交叉错误，相当于查寻一条横线与一堆竖线的第一个交点。本质是 FR 后继查寻问题。浮动错误类似。

对于询问操作，直接在处理 FR 后继的对应的平衡树上加入操作即可。删除询问操作类似。于是问题就变成了如何 FR 后继。

PR 查询一个数的后继是很简单的，操作分块来实现 FR 后继。复杂度 $\sqrt n\log n$ 。

事实上存在单次 $\log n$ 的 FR 查询后继的方法，感兴趣的可以自行查寻相关论文。它用到了许多有趣的科技，比如分散层叠和 vEBTree。