Top Tree 学习笔记

Posted by EtaoinWu on 周一 20 八月 2018

Reference:

  1. Renato F. Werneck, Design and Analysis of Data Structures for Dynamic Trees
  2. J. Holm, K. de Lichtenberg, and M. Thorup, Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
  3. J. Holm and K. de Lichtenberg, Top-trees and dynamic graph algorithms
  4. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Maintaining information in fully dynamic trees with top trees

注意这篇是笔记 、 不是教程 , 以后可能会出一份人类可读的版本 。

本文的 Top tree 均指 multilevel participation 的实现 。

本文不准备介绍操作复杂度定理的证明 , 因其过于复杂 。

Top tree: 基于树的 Contraction( 暂译 “ 合治 ”) 的动态树 。 维护的是一个无向的森林 。

将一棵树递归分成若干部分 ,top-down, 称作 “ 分治 ”; 反过来的过程 ,bottom-up 地把小块合并上来的过程 , 不妨称作 “ 合治 ”。

Clusters

为了实现这一目标 , 我们需要设立合治的单位 :cluster( 暂译 “ 树簇 ”, 对应物似乎是 “ 区间 “ 之于序列数据结构 )。 这玩意需要满足以下条件 :

  1. 有一个 \(O(1)\) 的边界 ( 否则信息存不下 )
  2. 可以合并拆分 ( 废话 )
  3. 不仅能储存树链信息 , 还可以储存 ” 树块 ” 信息 ( 子树信息 )

经过思考 查阅 , 树簇相关的术语被定义为如下 :

  • 树簇 , 简称 : 树上的一个连通子图 , 有至多两个点和全树的其他位置连接
  • 这两个结点被称做 界点 Boundary Node。 \(\mathcal C\) 的界点记作 \(\partial\mathcal C\)
  • 不是界点的点被称做 内点 Internal Node, 记作 \(\mathcal C\setminus \partial{\mathcal C}\)
  • 这两个界点之间的路径被称做 簇路径 Cluster Path, 记作 \(\pi(\mathcal C)\)
  • 有一个界点的被称做 叶簇 (Leaf cluster), 其余的称作 路簇 (Path cluster)
  • 最小的 ( 最基本的 ) 簇是树的一条边 , 称作 簇元 Edge cluster。“ 元 ” 字取其基本元素之意 , 或译 “ 簇素 ”, 然其音有误解之可能 。 如果连接的是叶子与其他 , 那么有一个界点 , 称作 leaf edge cluster; 反之有两个 , 称作 path edge cluster ( 不出现 , 不译 )。
  • 如果两个树簇 \(\mathcal A,\,\mathcal B\) 有且仅有一个公共点 ,( 显然此时这个公共点是二者的公共界点 ), 两个连通子图的并也是一个簇 , 那么他们被称做 可合并 (Mergeable), 合并的结果记作 \(\mathcal A\cup \mathcal B\)

考察一下合并的几种可能形态 。

 图 1: 合并的可能形态

另外 , 由于我们的递归结构在顶层会遇到问题 ( 并没有 “ 向外的边 ” 给全树这个簇用 ), 引入一个叫 External Boundary Node 的概念 ( 例外界点 )。

此时我们就定义好了 top tree 的基本 。

The Tree

那么这棵树是什么样子的呢 ? 由于 cluster 是二合一合并 , 将其直接记录下来就好了 。

  • 一个簇对应一个结点
  • 每个簇要么是叶子结点 ( 簇元 ), 要么是由两个簇合并起来 , 将他们作为大簇的孩子
  • ( 父亲 / 祖先 / 后代定义略 )
  • 如果一个簇是另一个簇的父 / 子 / 祖先 / 后代 , 且他们的簇路径有至少一条边的交 , 那么分别称作 path-ancestor/path-descendant/path-child。

于是就有了树结构 。

我们考虑一下这棵树的若干性质 。

  • 一颗 Top tree 中 , 同一个点在一层只作为一个簇的内点 。 因此一个点只作为 \( O(\log n)\) 次内点 。
  • 另外 , 由于我们同时要讨论原树和 Top Tree, 我将使用 “ 簇 ” 或 “ 簇结点 ” 指称 Top Tree 上的结点 。

The Operations, Black-box Flavored

那么这棵树支持什么操作呢 ?\(\def\defopname#1{{\newcommand{#1}{{\operatorname{#1}}}}}\def\opname#1{{\defopname{#1}\mathbf{#1}}}\)

\(\opname{Link}(v,w)\) : 假设 \(v,\,w\) 两个结点在不同的树 \(\mathcal T_v,\,\mathcal T_w\) 中 。 建立一颗新的 Top Tree \(\mathcal T\), 代表 \(\mathcal T_v \cup \mathcal T_w \cup \left\{(u,v)\right\} $ 。 $\opname{Cut}(v,w)\): 在 \(\mathcal T\) 中去除 \((v,w)\) 这条边 , 建立 \(\mathcal T_v\)\(\mathcal T_w\)
\(\opname{Expose}(v,w)\) : 将 \(v\)\(w\) 设定为 \(\mathcal T\) 的例外界点 。

这些操作暴露给外部 , 称作 外部操作 ; 是通过调用一系列内部操作来实现的 。 内部操作有以下这些 :

\(\opname{Merge}(\mathcal A,\mathcal B)\): 将可合并簇 \(\mathcal A\)\(\mathcal B\) 合并 , 创建 \(\mathcal C=\mathcal A\cup\mathcal B\) 作为他们的父簇 , 并 \(\partial\mathcal C=\partial(\mathcal A\cup\mathcal B)\) 。 设定 \(Info(\mathcal C):=\Merge(\mathcal C:\mathcal A,\mathcal B)\), 其中 \(\Merge(\mathcal C:\mathcal A,\mathcal B)\) 是用户定义的计算信息合并的过程 。
\(\opname{Split}(\mathcal C)\): 其中 \(\mathcal C=\mathcal A\cup\mathcal B\)。 调用 \(\Split(\mathcal C:\mathcal A,\mathcal B)\), 然后把 \(\mathcal C\)\(\mathcal T\) 中删去 。\(\Split(\mathcal C:\mathcal A,\mathcal B)\) 是用户定义的用 \(Info(\mathcal C)\) 更新 \(Info(\mathcal A)\)\(Info(\mathcal B)\) 的过程 , 可以理解为标记下传 。
\(\opname{Create}((v,w))\): 创建一条新边 。 调用同名用户定义过程 。
\(\opname{Eradicate}(\mathcal C)\): 要求 \(\mathcal C\) 是一个簇元 。 删除这条边 。 调用同名用户定义过程 。

这样 , 我们就可以把 Top tree 描述成一个黑盒 : 用户提供四个内部操作同名过程负责信息的维护 , 然后调用外部操作进行修改树结构 , 然后对根节点进行查询 。

Usages

我们考虑这玩意的可能用途 。

树形态的维护

\(\Link\)\(\Cut\) 已经提供了 。 考虑 \(\opname{LCA}\) , 可以定义成 \(\opname{YCenter}(x,y,z)​\) 表示这三个点所形成的 Y 字形的中间那个点 。( 待补 )

Sone1

每个簇维护以下东西 :

  • 除簇路径外的内点 点权和 、 最大值 、 最小值
  • 簇路径点权和 、 最大值 、 最小值
  • 除簇路径外的内点 点权标记 , 可以写成 \(x\leftarrow kx+b\) 形式
  • 簇路径点权标记 , 同理

\(\Merge\) 中处理加和 、 取 \(\operatorname{max}\) , 在 \(\Split\) 中把标记扔到两个孩子簇上 。

( 咦似乎这样甚至可以做子树 / 树链赋值 , 但是原题没有 )

动态直径 / 中心类的

待补 ; 见于 Non-local Search 部分 。

The Construction

先不考虑维护信息 , 只考虑树结构 。 我们先考虑一个暴力的构建 。 事实上有人 [citation needed] 尝试过自顶向下的分治出一棵 Top Tree 来 , 不过似乎没有什么结果 。 我们考虑自底向上的构建 : 每次拿到一棵树 , 进行一些合并 , 合并完的 cluster 每个都作为一条边放到上层 。 在同一层一个簇只会被合并一次 , 因此这里簇等价于底层的边 , 以下将混用 。

我们强行 ( 随意地 ) 给每个结点周围的边定一个极角序 。 这样 , 就可以定义出每条弧在顺向的前驱后继边 ; 显然构成了一个边的循环欧拉序 。

考虑两种基本的合并 :Rake 和 Compress。

 图 2:Rake 与 Compress

\(\opname{Rake}(x)\)\(x\) 是一个叶子结点 ; 将 \(x\) 合并到他往上连的顺向边上去 。 \(\opname{Compress}(x)\)\(x\) 是一个度为 \(2\) 的结点 ; 将 \(x\) 两侧的边合起来 。

对于每一层 : 使用一个数据结构 ( 欧拉序循环链表 ) 维护尚未被合并的簇 ; 一开始每个簇没有父亲 ; 然后遍历链表 , 随意地选择合法位置 ( 指那些要合并的两条簇都没有父亲的 ) 进行 \(\Rake\)\(\Compress\), 把结果作为两条簇的父亲 ; 直到没有合法的位置为止 。 实现上 , 为了给每一个簇结点一个清晰的层次 , 可以给每一个孤儿建一个父亲 , 这个父亲没有其他孩子 , 且与孩子其维护的簇是相同的 。 然后 , 把所有父亲作为上一层的边使用 。

然后操作层数 (Top Tree 的深度 ) 就只有 \(O(\log{n})\) 了 。 这里的证明比较简单 , 分为三步 :

  1. 读者自行验证 : 每棵树都有至少 \(\frac 12\) 的点度为 1 或 2。
  2. 简单讨论一下 , 不难证明 : 每个 \(\Rake/\Compress\) 操作至多只会让两个相邻的原本合法的操作失效 。
  3. 因此每层至少可以减少 \(\frac 16\) 的边 。
  4. 事实上有一些反例违反了 “ 每个 \(\mathrm R/\mathrm C\) 操作至多只会让两个相邻的原本合法的操作失效 ”, 但我们可以证明 , 假设有 \(k\) 个反例 , 那么度为 1 或 2 的结点至少有 \(\frac 12 N+k\) 个 。

然后这样我们就有一个 \( O(n)\) 的构建算法了 , 我们称作 \(\opname{Build}\)。 在构建算法过程中 , 我们可以指定例外界点 , 以符合特殊需求 。

The Operations, Detailed

现在来实现 \(\Link\)\(\Cut\) 。 我们先从暴力的方法来从 \(\mathcal T\) 构造出结果 Top Tree \(\mathcal T'\)

  1. 炸掉整棵树 。
  2. 重新 \(\Build\)
  3. \(\Build\) 的时候 , 每当 “ 随意地选择合法位置 ”, 改为 “ 先选择 \(\mathcal T\) 中做过的 、 现在仍合法的决策 , 如果没有再随意选择 ”

这是一个正确性显然的做法 , 因为其得到的 \(\mathcal T'\) 仍然是一棵合法的 ( 可能被 \(\Build\) 出来的 )Top Tree。

来看复杂度证明 。( 我不准备给出完整的证明 ) 我们只要证明 , 每层被影响到的 、 被重建的簇结点只有 \(O(1)\) 个 。 这很直观 , 但其证明非常复杂 。 完整正确的证明可见参考文献 [1]。

现在考虑 \(\Link/\Cut\) 的具体实现 。 同样 , 只考虑树结构 , 不考虑簇信息的维护 。

对于每一层 : 使用一个数据结构 ( 欧拉序循环链表 ) 维护尚未被合并的 、 被影响过的 簇结点 ; 一开始每个簇没有父亲 ; 然后遍历链表 , 随意地选择合法位置 ( 指那些要合并的两条簇都没有父亲的 ) 进行 \(\Rake\)\(\Compress\), 把结果作为两条簇的父亲 ; 直到没有合法的位置为止 。 最后 , 给每一个孤儿建一个父亲 。 然后 , 把所有父亲作为上一层的边使用 。

( 很显然 , 上文这段的撰写特意参照了 \(\Build\) 里面同样结构的一段 。)

至于 \(\Expose\)\(\Expose(v,w)\) 的 ( 一种可取 ) 实现是这样的 : 我们把所有包含 \(v,\,w\) 作为内点的簇拿出来 , 炸掉 、 暴露出其内部结构 ( 形成一个 \(O(\log n)\) 条边的临时树 ), 然后拿构建算法去 \(\Build(\mathcal T:\partial\mathcal T=\{(v,w)\})\)

最后额外地来考虑信息的维护 。 事实上对于 \(\Link\)\(\Cut\) 我们需要干的事情比较奇怪 : 我们先 ( 虚的 ) 做一遍上文描述的自底向上的东西 , 找到哪些结点要被 \(\Split\)\(\Eradicate\) 掉 , 然后自顶向下地 \(\mathrm S/\mathrm E\) 它们 , 然后再自底向上地 \(\Create/\Merge\) 回来 。

到这里 , 本体的做法就差不多讲完了 。 代码是不可能有的 , 这辈子都不可能写的 。

Non-local Searching

待补 。