更快(?)的带权并查集

· · 算法·理论

后日谈请见 博客园版本 的结尾。

现在考虑这么一个问题:给定一张无向图,初始没有边,每个点维护一个信息。
支持:连边,连通块加,单点求值。
这里的信息不可逆。即可以加但是不可以减。
要求在线回答询问。

如果可逆的话这自然就是普通的并查集。
但是不可逆会导致我们无法直接令 fa[a] = b,需要先对 b 进行 pushdown。
不巧的是,带路径压缩的并查集,一个点的子节点数量是充分多的。然后复杂度就爆了。

这里给一个均摊 O(\alpha(n)) 的带权并查集。并且算法流程还算简单。

前置知识

  1. 并查集

按秩合并路径压缩的那种。请自行学习。

  1. 二进制分组

这是一个把任意合并强制改造成启发式合并的技术。
具体来说,若一个集合大小为 k,那么其会被分成至多 \log k 块,且每块的大小都是 2 的幂。
当我们合并两个集合的时候,直接把所有块放一起,大小相同的块会被合并在一起变成更大的(显然还是 2 的幂),直到没有大小相等的块为止。

不难发现这样做的好处是,每次合并的两个块大小都相等,且每个集合至多 \log 个块。

  1. 迭代对数

下面复杂度中会出现 \log ^{*} n,这个描述的是 n 在不断取对数经过多少次会变成 \le 1 的数。
大概就是 \log ^{*} n = (\log ^{*} \log n) + 1 的样子。

  1. 某个递归式
可以证明 $T(n) \in O(n)$。 我们换个元,先令 $S(n) = T(n) + \sqrt n$,得到 $S(n) = \max_a S(a) + S(n - a) + \sqrt n - \sqrt {n - a} \le \max_a S(a) + S(n - a) + \frac{a}{\sqrt n}$。 我们不妨把 $\frac{a}{\sqrt n}$ 的贡献均摊到那 $a$ 个元素上。 于是对于任意一个元素,其领到的贡献值不超过 $\sum_k \frac{1}{\sqrt {2^k}} \le 147$。 5. 阿克曼函数 阿克曼函数的定义:$A(m, n) = A(m - 1, A(m, n - 1)), A(0, n) = n + 1, A(m, 0) = A(m - 1, 1)$。 这个递归式看起来很抽象,不过我们可以换个写法。 令 $A_m(n) = A(m, n)$,然后将其记作第 $m$ 层运算。 然后有 $A_m(n) = A_{m - 1}(A_{m - 1}(... A_{m - 1}(0))))$,即第 $m$ 层运算实际上是对 $0$ 做 $n$ 次第 $m - 1$ 级运算。 这里我们有 $A_0(n), A_1(n) \sim n + O(1) A_2(n) \sim 2n + O(1) A_3(n) \sim 2^n A_4(n) \sim 2^{2^{...2^{n}}}

因此上面提到的迭代对数实际上近似于 A_4 的反函数。

最初版本

我们先来设计一个 O(\log n) 的。
什么叫只路径压缩就是对的。

不管了,二进制分组拿都拿出来了总是要用的吧!
考虑每个连通块进行二进制分组,每组维护一个按秩合并路径压缩的带权并查集。
整块修改就枚举每个组给根打 tag,查询不用管这个是并查集内部的事。
合并的话考虑,若两个连通块 a < b,我们就枚举 a 的每个组,然后放到 b 的相应位置(先不合并/进位)
我们发现我们这一步的复杂度是 O(\log a),显然远小于 \sqrt a,所以根据前置知识 4 我们知道这里的枚举是线性的。

然后是合并和进位的问题。合并两个组可以直接考虑新建一个虚点,然后把两个根连到这个虚点上。
两边大小相等所以这里符合并查集按秩合并的要求。
至于这里合并和进位的总次数,这个显然是 O(n) 的因为可以看成合并代价是 1 的启发式合并。

这样就完成了。我们发现复杂度瓶颈有且仅有修改的打 tag,是 O(\log n) 的。

不初版本

这里我们发现,其实建一个线段树维护 tag,就可以做到 O(\log \log n) 了。
不过这个不够纯粹,换成倍增分块吧!

我们发现每次合并的时候多一个 \log \min 的代价其实是可以接受的。
那么正好适配倍增分块。

具体来说,对于每个连通块,令第 k 个组的大小为 s_k,则我们将其编号为 \log s_k。
然后将 [2^i, 2^{i+1}) 组分到一块。
修改的时候给每个整块打 tag,查询依旧 O(1)。
做合并/进位的时候,我们发现合并大小为 k 的组的时候只需要把他所在的块的 tag 下放了,而这个块的规模是 O(\log k) 的。

所以其他部分复杂度还是没变,打 tag 成功降低到 O(\log \log n)。

不终版本

继续。合并的额外代价只有 \log k,还是太少了!
不妨把块划分的更大一点吧!

取 f_1 = (147.154)^{220},f_i = 1.01^{f_{i - 1}} + 1,然后以 f 为分界点进行分块。
这样的话,我们合并大小为 k 的组的时候 tag 下放的代价就 O(\sqrt k) 了。
这自然是好的,说明这部分依旧是线性。

然后根据迭代对数的定义,我们的块数就降低到 O(\log ^{*} n) 了。

最终版本

这个结构,好像还是有点太简单了。
我们发现瓶颈依旧只有打 tag。剩下的合并、tag 下放、查询,都是线性的。
是否可以继续嵌套?

我们来看第 i 个块,其管辖的区间大小是 O(A_4(i))。
即如果访问到这个块内的元素,那么 O(A_4(i)) 的重构代价是被允许的。
那么好,我们再在这些块上面继续分块。取 f_1 = 147, f_i = A_4(f_{i - 1}),然后以 f 为界进行分块。
嗯不难发现 f_i \sim A_5(i)。

然后继续往上分分块,直到剩余块数和我们迭代的层数同阶为止。
假设层数是 d,那么就有 A_d(d) \sim n,因此 d \in O(\alpha(n))。
层数和最上层的块数都对了,那么打 tag 和查询复杂度就平衡到 O(\alpha(n)) 了。

至于合并,我们不妨假设合并大小为 k 的组时候需要把上方的块全都 pushdown 一遍。这些块的大小都是 O(\sqrt k) 的,所以合并复杂度至多再乘一个 \alpha(n)。
不过这也没关系,反正本来是线性的。

(这里的分析其实不是太严谨。应该是每次划分找最小元素的块大小来决定划分的右端点,然后再证明这个东西和阿克曼函数一个增长速度。)
(不过没关系,道理是差不多的。。。)