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

Stage0

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

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

其一个更特殊的情景是当树退化成序列的情景：例如经典题目《花神游历各国》https://www.lydsy.com/JudgeOnline/problem.php?id=3211 的一个做法是利用并查集维护向右下一个不是$1$的元素。这可以看成一个以最右端节点为根的链上的并查集。

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

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

将树分块

正如题目《王室联邦》https://www.lydsy.com/JudgeOnline/problem.php?id=1086 中指出，我们可以对树在线性时间内分块，使得每一个块的大小在$[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算法和花神游历各国的并查集部分都被加速到了线性。

ljt12138的博客

博客