UOJ Logo ljt12138的博客

博客

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

2019-02-17 17:29:30 By ljt12138

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标准算法有三个步骤:

  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 < 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$的元素。这可以看成一个以最右端节点为根的链上的并查集。

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

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

将树分块

正如题目《王室联邦》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算法和花神游历各国的并查集部分都被加速到了线性。

评论

FancyDreams
图巨太强啦
FancyDreams
图巨太强啦

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。