LCA 标准算法和树上线性并查集

Stage0

某天深夜水群的时候给小朋友普及 Tarjan 算法求 LCA 的时间复杂度,被老鸽们指正应当是 $O(n+q)$ 而非$O((n+q)\alpha(n))$。最近阅读了一下 wiki 上指出的论文 1 学习了一下。

先放结论:RMQ 问题和 LCA 问题的最优复杂度都是 $O(n)-O(1)$ 的,线性复杂度的 Tarjan 需要做一些操作。

Stage1 : RMQ标准算法

通常我们所说的 RMQ 问题,即区间最值问题被描述为:给定一个数组和若干询问,每次询问一段区间中最小值/最大值。我们常常使用ST表或线段树来解决这样的问题,复杂度分别是 $O(n\log n)-O(1)$ 和 $O(n)-O(\log n)$。$O(f(n))-O(g(n))$ 表示预处理时间复杂度为 $O(f(n))$,每次询问时间复杂度为 $O(g(n))$。事实上,存在 $O(n)-O(1)$ 的RMQ算法,这样的算法通常称为 RMQ 标准算法。

RMQ 标准算法有三个步骤:

  1. 建立序列的笛卡尔树,将 RMQ 问题转化成 LCA 问题
  2. 通过树的欧拉序列,将 LCA 问题转化为 ±1 RMQ 问题
  3. 通过分块 ST 表解决 ±1 RMQ 问题

为了方便,我们之后所有的讨论都为求区间最小值。

建立笛卡尔树

序列的笛卡尔树被定义为:最小值所在的位置作为根,其左侧区间的笛卡尔树作为左孩子,右侧区间的笛卡尔树作为右孩子的一棵树。假设我们拥有了一个序列的笛卡尔树,一个很明显的自顶向下寻找 $[u, v]$ 区间最小值的算法如下:

  1. 如果第一个点在当前节点左侧,第二个点在当前节点右侧,则根节点就是区间最小值
  2. 如果在同一侧,则递归到该侧查询

我们事实上是在求$u,v$在笛卡尔树上的LCA。那么,$[u,v]$ 之间的区间最小值的位置,就是 $u, v$ 在笛卡尔树上 LCA 所表示的位置。

笛卡尔树可以被线性的建立。我们每次在序列右端新增一个节点,并维护笛卡尔树最右端的点 $rm$。对于每个节点 $u$,我们维护其父亲 $fa[u]$ 和其左右儿子 $lc[u], rc[u]$。新增一个节点 $nd$ 时,我们将其设为 $rm$ 的右孩子。之后,利用平衡树的旋转操作,不断向上旋转,直到 $nd$ 的父亲的值比其小为止,最后将 $rm$ 设为 $nd$。由于将 $nd$ 向上旋转不会破坏序列的左右顺序,也不会破话除 $nd, fa[nd]$ 两个节点之外父子的大小关系,最终得到的一定是原序列合法的笛卡尔树。

我们称 $nd, rc[nd], rc[rc[nd]], …$ 为笛卡尔树最右端的链,由于最右端的链长每次最多增加 $1$,而每次向上旋转会使得其长度减小 $1$,那么旋转的总次数是 $O(n)$ 的,因而建立笛卡尔树的复杂度也是 $O(n)$ 的。

转化为 ±1 RMQ 问题

一个常见的求 LCA 的算法是转而求解树的欧拉序列上的 RMQ 问题。所谓欧拉序列,就是对树做dfs,每当访问一条边 $(u,v)$ 时,就在序列上加入 $v$。特别的,序列上一开始只有根节点。设每个节点 $nd$ 出现的第一个位置为 $pos[nd]$,那么,两个节点 $u, v$ 的 LCA,就是 $[pos[u], pos[v]]$ 中最浅的节点。

欧拉序列良好的性质在于,任何两个相邻元素之间深度相差必然为 $1$。那么问题便被转化为了,给定一个序列,任意两个元素之间相差为 $1$,并给定若干个区间,求区间内最小的数。

±1 RMQ问题的线性解法

线性解决 ±1 RMQ 问题的关键在于,由于相邻两个元素之差为 $1$,那么长度为 $n$ 的本质不同的数列只有 $2^n$ 个。

考虑将序列按照长度为 $\frac{\log(n)}{2}$ 分段,我们可以认为 $\log(n)\le w$,$w$ 是计算机的字长(假设我们在随机储存器计算模型下)。长度为 $\frac{\log(n)}{2}$ 的本质不同的数列只有 $O(\sqrt{n})$ 个,我们可以枚举所有可能的情况,并枚举左右端点。这可以在 $O(\sqrt{n}\log^2(n))$ 的时间复杂度内完成。一个数列长度为 $n$ 的数列可以用二进制串编码,其第 $j$ 位为 $[a_{j} \lt a_{j+1}]$。

对于分成的 $O\left(\frac{n}{\log(n)}\right)$ 段,使用 ST 表维护区间最小值。这样可以做到 $O(n)$ 时间的预处理和 $O(1)$ 时间的询问。

考虑一个区间询问 $[u, v]$,可以看成一些整块和一些零散部分。对于整块,可以用 ST 表上 $O(1)$ 询问最小值;对于零散部分,通过查表求出答案。这样,总共的询问时间复杂度是 $O(1)$ 的,而所有预处理的复杂度都是 $O(n)$ 的。因此,我们给出了 $O(n)-O(1)$ 求解一般 RMQ 问题的解法。

Stage2 : 线性树上并查集

将 Tarjan 优化到线性的技术来源于线性树上并查集。树上并查集是并查集的一个特殊情况:给定一棵树,每次操作形如将一个节点合并到父亲,每次询问形如查询一个点已合并的祖先。

其一个更特殊的情景是当树退化成序列的情景:例如经典题目2的一个做法是利用并查集维护向右下一个不是$1$的元素。这可以看成一个以最右端节点为根的链上的并查集。

树上线性并查集的做法分为三步:

  1. 将树分为大小为 $O(b)$ 的块,且块的个数是 $O(n/b)$ 的
  2. 对于每种本质不同的块的本质不同的状态,预处理每个点的答案
  3. 对块间维护并查集

将树分块

正如题目3中指出,我们可以对树在线性时间内分块,使得每一个块的大小在 $[b, 3b]$ 之间,且每一个块有一个“根”。满足每个块 $B$ 都与其根联通,且 $B$ 在其根的子树内。

使用一个 dfs 过程可以将树分块。在 dfs 所有子树后,我们将子树中剩下的节点($\le b$ 个元素的零散块)合并,剩下至多一个零散块。这样可以保证,除了根节点可能有一个大小为 $2b < size\le 3b$ 的块,其他的块大小都在 $[b, 2b]$ 之间。

预处理

考虑本质不同的树至多有多少个,一棵树可以被父亲数组 $parent[nd]$ 唯一确定,而 $parent$ 数组可以被编码到长度 $(b-1)\times \log b$,那么本质不同的树的上界就有 $2^{(b-1)\log b}$ 种。对于每种本质不同的树,每一个节点可以被操作过,也可以没有被操作过,本质不同的状态有 $2^b$ 个,那么每种本质不同的状态中每个节点的答案一共有:

如果我们取 $b=\log\log n$,那么上式是 $O(n)$ 的。

对块间维护并查集

我们对块间,即所有的“根”维护并查集。由于并查集的节点数只有 $O(n/b)$,当我们取 $b=\log\log n$ 时,总复杂度是 $O(n/b\alpha(n)+q)=O(n+q)$ 的。

对于一个将节点合并到父亲的操作:可以 $O(1)$ 修改块状态完成。

对于一个查询操作:如果当前块内已经合并到块的根了,向上查询。如果一个节点是某个块的根且合并到了其父亲,使用一个并查集合并上去。

这样,我们就在 $O(n)-O(1)$ 的时间复杂度内解决了树上并查集问题!自然,Tarjan算法和花神游历各国的并查集部分都被加速到了线性。

参考文献

1. Gabow H N, Tarjan R E. A linear-time algorithm for a special case of disjoint set union[J]. Journal of Computer and System Sciences, 1985, 30(2): 209-221.
2. 《花神游历各国》https://www.lydsy.com/JudgeOnline/problem.php?id=3211
3. 《王室联邦》https://www.lydsy.com/JudgeOnline/problem.php?id=1086

本文标题:LCA 标准算法和树上线性并查集

文章作者:ljt12138

原始链接:http://ljt12138.github.io/2019/08/08/linear-dsu/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。