由斜二倍增引发的思考 / 线段树的多版本线性空间复杂度追加

· · 算法·理论

（图一）

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

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

在树上多版本实现的时候，在深度为 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} 线段树。因此每棵树需要记录这个根到其紧挨的前一棵树的根的指针以便跳跃。斜二倍增则相对自然些，一棵树最左叶子结点向左走一步即为紧挨的前一棵树的根。

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

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

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

斜二倍增很优美。下面是我对它 \mathcal O(1) 增量空间复杂度的理论总结。

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

我通过 @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) 添加的多版本结构。

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

仅供娱乐。