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

Stage0

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

先放结论：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 标准算法有三个步骤:

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

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

建立笛卡尔树

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

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

我们事实上是在求$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 优化到线性的技术来源于线性树上并查集。树上并查集是并查集的一个特殊情况：给定一棵树，每次操作形如将一个节点合并到父亲，每次询问形如查询一个点已合并的祖先。

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

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

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

将树分块

正如题目³中指出，我们可以对树在线性时间内分块，使得每一个块的大小在 $[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$ 个，那么每种本质不同的状态中每个节点的答案一共有：

$2^{(b-1)\log b}\times 2^b\times 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算法和花神游历各国的并查集部分都被加速到了线性。

参考文献

¹. 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. ↩

². 《花神游历各国》https://www.lydsy.com/JudgeOnline/problem.php?id=3211 ↩

³. 《王室联邦》https://www.lydsy.com/JudgeOnline/problem.php?id=1086 ↩