由斜二倍增引发的思考 / 线段树的多版本 O(1) 复杂度追加

· · 算法·理论

（图一）

最近学习了优美的斜二倍增。以下是我对它 \mathcal O(1) 增量空间复杂度的理论总结。

斜二倍增 = 满二叉树的后序遍历序号对应每个点的森林结构。

线段树也可以做到多版本增量 \mathcal O(1) 空间复杂度。如图所示，每个位置下面存自身信息，上面只保存一个区间信息。也可以用位运算计算出每个森林的根，比斜二倍增复杂一些。这里的线段树也是类似于树状数组那种左子树 2^k 大小的，而不是平均分段。图中 ×, ∗, ✳︎, ⛤ 的位置也非常有规律，可以考虑在 DFS 的过程中作为临时空间使用。

这意味着，非要用线段树来解决一棵树只增加叶子结点并 query 一条边的问题，也可以用总共 \mathcal O(n) 空间复杂度来实现。什么时候非要用线段树而不是用二叉树呢？两者好像没有本质区别。试举一例的话，例如高阶矩阵乘法，线段树上每个点是乘 1 次，二叉树是乘 2 次。

（图二 真正的 {{3}\over{2}}）仔细的你可能已经发现，图一中，每个二阶的子树最正确的摆放位置应该比图中更靠后 1 位，每个二阶以上的子树最正确摆放位置应该比图中靠前 1 位，这样可以保证区间信息和当前位置所存的信息完全独立。计算量方面有一点微小的代价。

考虑一整棵树上存着这些东西，可以发现还有很多冗余存储，例如从根到深度为 16 的结点路径的信息在它的子树所有深度为 24 的点都存了一份。全盘考虑之下，冗余信息的密度相当的高，是否还可以继续整活呢…

实用性一般，仅供娱乐。因为：

在树上多版本实现的时候，在深度为 d (根的深度为 0) 的线段树版本为 1+\Bigl\lfloor\log\Bigl( \bigl\lbrace{\footnotesize\begin{array}{ll}d, && \textrm{figure 1}\\d+1, && \textrm{figure 2}\end{array}}\Bigr)\Bigr\rfloor 个树组成的森林，每棵树的根的位置相对于其叶子结点过于偏远，相当于其所有叶子的儿子中点再加上叶子的总量，某种意义上可以称它为斜率 {3}\over{2} 线段树。因此每棵子树需要记录左右儿子的指针以便跳跃。森林中每棵树根之间也要通过指针来跳跃。斜二倍增则直观、自然，一棵树最左叶子结点向左走一步即为紧挨的前一棵树的根，其他结点的右儿子的位置也是向左走一步。

树上的版本追加一个叶子的时间复杂度取决于森林中不同树根间的指针维护。这不太平凡，分为两个问题：合并两棵树、寻找需要合并的树。寻找需要合并的树可以通过树的大小、在追加的结点深度的二进制求得，即合并两棵最小的大小相同的树，但是这里不考虑大小为 1 的树（图一图二是不同的情况），或者从二进制看，合并的树的大小若是 2^k，则任意 2^j < 2^k 大小的树均存在。但指针的维护是另一种方式，每次合并两棵树得到新的一棵树时，可以“简单地”判定它将来是作为左子树被合并，还是作为右子树合并左侧的某棵树，即“合并者”。从位置上考虑，两棵合并的树根几乎都是被一个更大的树根隔开的，也就是说距离至多是 2。可以用 O(1) 时间维护“合并者”链，这个链的 head 即为每次需要合并的树根（大小为 1 的树仍然是特判）。所有的“被合并者”也按照顺序连成一条链，维护也是 O(1) 的，可以用于合并两棵树的操作。注意每个“合并者”也需要指向它生成时所对应的“被合并者”，这时需要用到距离至多是 2 的性质，可能需要在“被合并者链上”多走一步。合并的时候好像还需要维护“被合并者”链，那就不维护了，呵呵，没事的，从这里断掉了（“简单地”判定一下吧），会从刚才那个“合并者”指向的“被合并者”接起来的。

回到最初的问题，真的是因为开不起 \mathcal O(n\log n) 的空间吗？还是优美（且高效）最重要吧。

我通过 @ftiasch 的这篇文章了解斜二倍增时，做了一些思考，结论是

只添加多版本数据结构可以做到：单版本平均空间复杂度 \le 平均追加时间复杂度 作为 增量空间复杂度

因此想到线段树也可以改进成 \mathcal O(1) 增量空间的结构，故作上图和本文说明之。相关思考内容如下：

多版本 \mathit{DS} 每个新版本之中，尽管增加/修改了 \mathcal O(\log n) 个结点，但只有 \mathcal O(1) 个点所存的内容在所有未来版本是固化的。只保存这个固化的点。其他的时间换空间随用随算。满二叉树后序遍历满足 \mathit{DS} 所需的 \mathcal O(1) 固化性质。用后序遍历序号对应满二叉树的每个点即得。\mathit{DS} \neq 线段树，因为线段树数据只存叶子上。

满足 \mathcal O(1) 固化性质的多版本数组数据结构还有其他选项吗，用分形的思想，假设在某点 X 位置这个版本的数据结构正好“满了”，既然满了且固化了，即可认为最多还有 \mathcal O(\log n) 规模的信息可以不保存，此外即是数据结构本身。满的版本 X 的数据结构用 (\mathit{DS}(k), \mathit{Info}(k)) 描述。

考虑版本 Z > Y=(\mathit{DS}(k)+\mathit{DS'}(k),\mathit{Info}(k)+\mathit{Info}'(K))以及Z=(\mathit{DS}(k+1), \mathit{Info}(k+1)) 。代表从 X+1 到 Y 的所有增量的区间 [X+1, Y]、 Z 都是满的。 Z-X-Y=(R(k), \mathit{DI}(k)) 。 R(k) 如非空，其中必然要保存新增的数值的*。这就是类后序遍历性质。

如果不想要*，就更加有趣了。显然 R(k) 之中必有结构，除非分别装进 \mathit{DS'}(k) 和 \mathit{DI}(k) 之中；\mathit{Info}(k) 也可以装进 \mathit{DS'}(k) 中。这几乎可以证明追加操作时间复杂度均摊 \mathcal O(1) 的数据结构都可以改装成空间复杂度 \mathcal O(1) 添加的多版本结构。

完成这篇文章我才知道，把多版本线段树的空间复杂度增量做到 O(1) 之后，向 \mathit{DS'(k)} 缝合 O(1) 树上场景追加的时间复杂度，远比这里写的 \mathit{Info}(k) 复杂得多。原本以为的从线段树中省略掉的 O(\log n) 规模的链，其实只是 \mathit{info}，最后做出来的数据结构是 \mathit{INFO}。

再举一个时空复杂度相互转化的例子，用斜二倍增思想建堆（结构完全相同），可以做到均摊 \mathcal O(1) 插入、\mathcal O(\log n) 删除最小的操作。总计 a 次删除 z 次插入任意次序的操作可以在 \mathcal O(a\log z + z) 时间内完成。但无法实现 decreaseKey ，故同样是仅供娱乐，以上。