树链剖分的两种方式:重链剖分与长链剖分

树链剖分是一种将有根树分解为若干条不相交路径的方法,可以看作是处理序列问题的数据结构或算法在树上进行推广的一种手段。但为了保证时间复杂度,进行分解时的路径选择需要满足一些规则,而根据具体问题不同,树链剖分的常用方式有重链剖分(heavy path decomposition)长链剖分(long path decomposition)两种,这篇文章将对这两种方法及它们所擅长处理的问题做一些介绍。

作为前置技能,这里默认大家比较熟悉树的dfs序倍增LCA

重链剖分

为了方便讨论,我们记节点\(x\)的父节点为\(fa[x]\),深度为\(dep[x]\),子树大小为\(sz[x]\)。此外,在重链剖分中需要引入一个新概念:重儿子(preferred child),节点\(x\)重儿子指\(x\)的子节点中,子树大小最大的节点,则除了叶子节点外,每个节点有且仅有一个重儿子。

每个节点与重儿子相连的边称为重边(preferred edge),重边以外的边称为轻边。我们将重边连接起来,所形成的极大的由重边组成的路径就称为重链(preferred path),重链剖分的核心就是将树分解为这样的重链,并对它们加以维护,使得对树链的修改、求和、求最值等问题可以被加速。

下图是重链剖分的一个例子,其中粗边表示重边,虚边表示轻边,图中的重链有\(A\rightarrow G\rightarrow H\rightarrow K\rightarrow L\)、\(B\rightarrow C\rightarrow E\)、\(I\rightarrow M\)、\(D\)、\(F\)、\(J\)共五条。注意,不与任何重边相连的节点也被记为重链,且由于重儿子不唯一(子树大小相同的儿子可以任选一个作为重儿子),重链剖分也是不唯一的。

wpg_div_wp_graphviz_1

有了重链剖分的结构后,为了解决树链相关的问题,我们需要把每次操作涉及的树链分解为重链和轻边的组合,考虑一棵有\(n\)个节点的树,这里会用到一条重要结论:从根节点到任意一个节点\(x\)的路径上,重链和轻边的数量均不超过\(O(\log n)\)。其大致证明如下:

考虑一条轻边\(x\rightarrow y\),必有\(sz[y]\leq\frac{1}{2}sz[x]\),否则\(x\rightarrow y\)一定是重边。那么假设从\(y\)到根节点一共经过了\(k\)条轻边,则\(sz[y]\leq\frac{n}{2^k}\),而\(sz[y]\geq 1\),所以轻边数量不超过\(O(\log n)\)。又因为重链和轻边一定是交替出现的,所以重链的数量也不超过\(O(\log n)\)。

有了这个结论后,我们只用让树链的两个端点分别向上走到它们的LCA即可完成分解。但这里有一个问题:虽然重链和轻边的数量都是\(O(\log n)\)的,轻边可以\(O(1)\)地向上走,重链却做不到。解决问题的方法是,对每个节点\(x\)再额外维护一个值\(top[x]\),表示\(x\)所在的重链中深度最小的节点编号,显然这个值不难通过dfs求得。这样一来,重链也可以做到\(O(1)\)地向上走,故对一条树链分解的总时间复杂度为\(O(\log n)\)。

下图是对树链\(F\rightarrow L\)分解的一个例子,其中树链经过的轻边由红色表示,经过的不同重链由不同颜色表示。注意这条树链只经过了重链\(B\rightarrow C\rightarrow E\)的一部分,这是允许的,我们也可以通过\(top[C]\)的值快速通过这条重链。

wpg_div_wp_graphviz_2

接下来考虑树链上的修改和询问操作,对于轻边,我们直接\(O(1)\)地进行操作即可,对于重链,我们可以通过维护树的dfs序来进行快速操作。为了能够用线段树等数据结构进行维护,我们必须将同一条重链上的点映射到一个连续的区间,这并不困难,我们只需规定对每个点dfs时先遍历它的重儿子,最后重链上的点映射到序列里便是连续的,例如上图的dfs序应为\(AGHKLIMJBCEDF\)。

为了实现重链剖分,我们首先需要两次dfs:第一次dfs用于求出重儿子和计算其它信息,第二次dfs用于计算\(top\)数组和dfs序。当操作一条树链时,我们可以类比倍增LCA的询问,每次令\(top\)的深度较大的节点向上跳一段重链,并统计相关信息,知道两个节点位于同一条重链上,再统计它们之间的信息即可。

由于使用了dfs序,所以重链剖分处理子树问题也很方便。重链剖分所需的空间复杂度是\(O(n)\)的,时间复杂度则取决于维护dfs序所用的数据结构:如果采用线段树、Treap或Splay,时间复杂度为\(O(n\log^2 n)\),如果采用树套树,时间复杂度为\(O(n\log^3 n)\),如果采用全局平衡二叉树,则可以证明此时复杂度为\(O(n\log n)\)。

不难发现将重链的信息拼接起来这点,很类似于线段树两个区间的信息合并,所以线段树擅长处理的问题,放到树上就是重链剖分擅长处理的问题,[ZJOI2011]道馆之战就是一个不错的例子。

长链剖分

简单来说,只需将重链剖分中的preferred child由子树节点数最多的儿子改为子树高度最大的儿子,我们就得到了长链剖分结构。长链剖分可能与重链剖分是相同的(例如这篇文章的第一个例子),下图则是一个长链剖分与重链剖分不同的例子。

wpg_div_wp_graphviz_3

但在长链剖分中,一个节点到根的路径上轻边和长链的数量就不是很优秀了。具体来说,考虑一个叶节点\(x\),在下述情况下,\(x\)到根节点的路径可能全部由轻边构成:\(x\)的父节点有至少一个除\(x\)外的儿子,\(x\)父节点的父节点有至少一个不包含\(x\)且深度不小于\(2\)的子树,以此类推,根节点有至少一个不包含\(x\)且深度不小于\(dep[x]\)的子树。不难发现,在这种情况下,\(x\)到根节点的路径就由\(O(\sqrt n)\)条轻边和长链构成。

当然,长链剖分也不是毫无用武之地,在某些问题上,使用长链剖分可以得到更优秀的复杂度,比如我们下面将解决的问题:对于一棵\(n\)个节点的有根树,要求在线询问某个节点的\(k\)倍祖先。容易知道,借助重链剖分或倍增LCA,我们可以得到一个\(O(n)-O(\log n)\)或\(O(n\log n)-O(\log n)\)的算法,而借助长链剖分,我们可以做到\(O(n\log n)-O(1)\)的时间复杂度。

在介绍算法流程之前,我么先介绍需要用到的一个结论:在长链剖分结构中,任意一个节点的\(k\)倍祖先所在的长链,其长度不小于\(k\)。证明如下:

如果该节点和其\(k\)倍祖先在同一条长链上,则这条长链长度当然不小于\(k\),否则其\(k\)倍祖先有一个除该节点外深度不小于\(k\)的子树,那么其\(k\)倍祖先所在长链长度当然也不小于\(k\)。

有了该结论后,我们先求出树的长链剖分结构和倍增LCA数组,并额外维护如下信息:对于一条长度为\(k\)的长链中深度最小的节点\(x\),暴力求出\(x\)的前\(k\)倍祖先与沿着长链向下的前\(k\)个子节点。由于所有长链的长度之和恰好为\(n\),所以\(O(n)\)的时间即可维护这些额外信息。

接下来考虑如何在线求出一个节点\(x\)的\(k\)倍祖先。首先假设不大于\(k\)的最大二进制数为\(k_b\),则先通过倍增LCA数组从\(x\)跳至\(x\)的\(k_b\)倍祖先\(x’\)处。由于\(k-k_b<\frac{k}{2}\),根据我们之前证明的结论,\(x’\)所在的长链长度应不小于\(k_b\),也就严格大于\(k-k_b\)。而我们已经预处理出了\(x’\)所在长链的顶端向上或向下的不少于\(k-k_b\)个节点,这一定覆盖了\(x’\)的\(k-k_b\)倍祖先,所以直接利用这个额外信息向上跳即可。

至此,我们介绍完了长链剖分的结构,并成功地用优于重链剖分的复杂度解决了在线\(k\)倍祖先查询的问题。当然长链剖分还有很多其他妙用,也不一定会用到我们之前证明的结论,但在大家都很熟悉重链剖分的情况下,如果有时候发现重链剖分的复杂度偏高,考虑长链剖分是否能够更优总是一种好的尝试。

关于 “树链剖分的两种方式:重链剖分与长链剖分” 的 1 个意见

  1. 其实链剖+Splay可以证明是O(nlogn)的(不过也没有什么用233).

发表评论

电子邮件地址不会被公开。 必填项已用*标注