学习笔记 - 信息学竞赛中的持久化数据结构与技巧
1-1 信息学竞赛中的持久化数据结构与技巧
一、持久化（persistent）的概念
- 持久化 不是 可持久化。
- 对数据结构修改后，修改前的版本仍然存在。
二、对数据结构的操作一般分为几类 :
查询: 输入一个或多个数据结构，只查询信息不做任何修改；
修改：输入一个数据结构以及对它的修改方式，输出修改后的数据结构
合并：输入多个数据结构，输出这几个数据结构合并后的成为的一个数据结构；
三、部分持久化
- 数据结构的不同版本构成一个序列，其中每一个版本都可以被查询，但只有最后一个版本可以被修改。
- 每次修改导致序列末尾增加一个新元素。
- 这个序列称为版本序列。
$e.g.$
原序列：$1,2,3$（第一个版本）
将 $2$ 修改为 $1$：$1,1,3$（第二个版本）
将 $3$ 修改为 $4$：$1,1,4$（第三个版本）
所有的版本构成一个序列，每次只能修改最后一个版本得到新的版本加入序列叫做 部分持久化。
四、完全持久化
- 数据结构的不同版本构成一棵有根树，每个结点是由其父亲修改得到的。
- 每次可以从指定的版本中进行修改的到新的版本。
- 每次修改导致有根树新增一个叶子。
- 这个树结构称为版本树。
$e.g.$
原序列：$1,2,3$（第一个版本）
将 $2$ 修改为 $1$：$1,1,3$（第二个版本）
将 $3$ 修改为 $4$：$1,1,4$（第三个版本）
以上是一个版本序列，如果是部分持久化只能从第二个版本进行修改，而完全持久化可以从任意一个版本的基础上进行修改。
$e.g.$ 由第二个版本修改得第四个版本 $5,1,3$，还可由第一个版本得第五个版本 $6,2,3$ 等等。
那么整个从指定版本中修改得到新的版本的过程就构成了一颗版本树，如图，$1,2,3,4,5$ 代表版本编号，$1$ 是根。
五、可合并的持久化
数据结构的不同版本构成一个有向无环图，每个结点由其前驱 合并 或 修改 得到。对于一次合并操作，几个数据结构版本被 合并 为一个新的数据结构版本，新建的结点的前驱是被合并的结点的一次修改操作，新建的结点的前驱是被修改的一个结点，是由合并结点拼接而成的。这个图称为版本图。
$e.g.$
如图，版本一和版本二就合并成了版本三，版本三由版本一和版本二拼接而成，版本四也同理。
六、离线处理持久化问题
- 部分持久化离线后按时间升序扫版本序列，相应进行修改查询。
- 完全持久化离线后对版本树进行 DFS，相应进行修改、撤销修改、查询；修改一般不能带均摊。
七、持久化常见方法
7.1. 路径复制（path copy）
- 要求数据结构按有根树存储。
- 每个结点有指向每个孩子的指针，没有其它指针。
- 修改或查询中，访问一个非根的结点必须先访问它的父亲。
- 修改时，如果需要修改某个结点，则复制一份再修改。
- 修改时，如果一个节点的孩子被修改，则这个结点也发生修改，需要将指向孩子的指针改为指向修改后的孩子的指针。
- 如果需要新建结点，则直接新建。
- 如果需要删除结点，则只能删除不被任何指针指向的结点。
- 不改变原数据结构的单次修改/查询的时间复杂度。
- 空间复杂度和时间复杂度相同。
- 对数据结构的结构有限制。
- 支持部分持久化、完全持久化、可合并的持久化。
- 对于带均摊时间复杂度的数据结构，因为同个版本可以被多次修改，可能被卡掉最坏情况。
- 应用：
1.$\ $栈（push/pop/top）
2.$\ $线段树（单点/区间/修改/查询）
3.$\ $平衡树（单点/区间/修改/查询，分裂/合并）
4.$\ $可并堆
7.2.1.1. 肥结点（fat node）- 部分持久化
- 对原数据结构的内存中的每个位置的值，维护其经历的每次修改的时刻和修改后的值。
- 相当于部分持久化数组。
- 记对值的修改次数为 $m_1$，对值的査询次数为 $m_2$。
- 使用带末端插入的数组，查询时二分查找，时间复杂度为 $O((m_1+m_2)\ log\ m_1)$，空间 $O(m_1)$。
- 若使用 vEB 树，则时间复杂度可以降低到 $O((m_1+m_2)\ log\ m_1)$。
7.2.1.2 补: $O(log\ n)-O(1)$ 的动态标号法
- 问题描述：维护双向链表，支持在给定结点前后插入，查询两个结点的先后关系。
- 使用重量平衡树（单点插入时只改变 $O(log\ n)$ 个结点与根的相对位置）维护节点的顺序。
- 在平衡树上每个结点维护一个区间，根对应 $[0,2^w-1)$。
- $[l,r)$ 的左右孩子分别对应 $[1,(1+r)/2)$，$[(1+r)/2,r)$。
- 如果一个结点与根的相对位置发生改变，则重新计算结点对应的区间
- 每个结点对应的标号是 $(1+r)/2$
- 插入结点的时间复杂度是 $O(log\ n)$
- 比较结点的先后关系只需 $O(1)$ 比较标号
7.2.2.1 肥结点（fat node）- 完全持久化
- 考虑版本树的括号序列，将其视为一个等效的修改序列
- 每次对值的修改相当于在序列中插入两次修改操作
- 使用 $O(log\ n)-O(1)$ 的动态标号法维护等效的修改序列中的时刻
- 使用平衡树维护每个值的修改序列的插入和查询
- 时间复杂度 $O((m_1+m_2)\ log\ m_1))$，空间 $O(m_1)$。
- 如何改进 （见 $7.2.2.3$）
7.2.2.2 补：$O(1)-O(1)$ 的小规模动态标号法
- 问题描述：维护双向链表，支持在给定结点前后插入，查询两个结点的先后关系；结点不超过 $w$ 个。
- 初始化时，给链表每个结点分配等差数列编号，且链表首尾的差充分大。
- 插入结点时，标号为前驱和后继的标号的平均数。
- 插入结点的时间复杂度是 $O(1)$。
- 比较结点的先后关系只需 $O(1)$ 比较标号。
- 可以嵌套使用，处理结点不超过 $w^{O(1)}$ 个的情况，每层结点超过 $w$ 个就分裂后重新初始化，并在上层插入一个结点。
7.2.2.3 肥结点（fat node）- 完全持久化 改进
- 对修改序列选出一些代表元。
- 用 $O(log\ n)-O(1)$ 的动态标号法维护代表元的标号。
- 维护性质:
修改序列中，相邻 $log^2(m_1)$ 个位置有至少一个代表元。
每个值对应的修改序列中，相邻 $log^2(m_1)$ 个位置有至少一个代表元。 - 每次插入修改操作，均摊增加 $\frac{1}{log^2(m_1)}$ 个代表元，改变 $\frac{1}{
log(m_1)}$ 个代表元的标号。 - 修改序列中，两个代表元间的 $O(log^2(m_1))$ 个修改操作，用 $O(1)-O(1)$ 的小规模动态标号法（嵌套两层）维护动态标号。
- 每个值对应的修改序列中，用 vEB 树维护代表元，在标号变化时删除并重新插入;用平衡树维护两个代表元间的 $O(log^2(m_1))$ 个修改操作，在非代表元变成代表元时分裂;支持 $O(log\ log(m_1))$ 查询后继。
- 时间复杂度 $O((m_1+m_2)\ log\ log\ m_1)$
7.3.1. 结点分裂（nodes splitting）
- 可以将路径复制和肥结点结合，得到结点分裂方法
- 要求数据结构按有向图存储
- 如果每个结点的入度和出度分别有常数上界，则可以使用结点分裂高效实现完全持久化
- 每个结点维护原数据结构上结点的常数个版本
- 完全持久化中，单个节点的修改对应于在相应结点上插入两个版本（如果修改了指针，指针两侧的结点都要插入版本）
- 一个结点 $x$ 上版本过多时，分裂为两个结点 $x$ 和 $x’$，此时需要相应修改与这个节点相邻的结点（给相邻节点插入一个修改操作，把指向 $x$ 的指针改为指向 $x’$）
- 结点上的版本个数足够多的时，分裂导致的递归分裂均摊是少的，单次修改是 $O(1)$ 的。
- 另外用 $O(log\ n)-O(1)$ 的小规模动态标号法维护每个版本的的标号，得到 $O(1)-O(1)$ 的动态的标号。
- 应用
1.$\ $双端队列
2.$\ $维护了父指针的平衡树
3.$\ $并查集
4.$\ $自底向上的动态树的持久化
八、持久化数据结构
- 持久化数组
- 持久化线段树
- 持久化平衡树
- 持久化可并堆
- 持久化动态树