似乎好久没有写博客了，其实写了一个EC-final游记，但是不太想发
今天来挖个坟，这是一年前我发的帖子关于并查集随机合并复杂度正确性，当时帖子底下有许多或对或错的感性证明。
在写带撤销并查集的时候，因为路径压缩只能保证均摊复杂度。所以往往需要写按秩合并，而这种随机合并的写法可以让你省去几秒钟的思考，省去几行代码，减少一点数组操作，增加一些常数。
今天又写了一个带撤销并查集的题，用到了这个写法。又想了想这种合并方法，似乎可以严谨证明，就写一下，以后可以放心这么写不被卡了。
注意：下文的证明基于以下这种先find再比较rnd的写法！别的写法可能被卡，详见上面帖子中我的回复
int find(int x){return fa[x]==x?x:find(fa[x]);}
void mrg(int x,int y){
x=find(x),y=find(y);
if(rnd[x]>rnd[y])swap(x,y);//其中 rnd[i] 是预处理的随机数
hist.push({y,fa[y]});
fa[y]=x;
}
定理. 上述这种写法中，无论以什么样的顺序合并，一个大小为 $n$ 的集合的期望高度是 $O(\log n)$。
证明.
不妨定义一棵树的指数高度为 $h=2^{d}$，其中 $d$ 是这棵树原本的高度。
记 $f(n)$ 为一个大小为 $n$ 的集合，其指数高度的期望。记 $g(n)$ 为一个大小为 $n$ 的集合，其高度的期望。
假设目前合并两个大小分别为 $n,m$ 的集合，他们的深度分别为 $d_n,d_m$。
如果合并时以 $n$ 为根，则合并后树的高度为：
\[\begin{aligned} d&=\max(d_n,d_m+1)\cr \Leftrightarrow h&=\max(h_n,2h_m)\cr &\le h_n+2h_m \end{aligned}\]以 $m$ 为根同理。
引理. 以大小为 $n$ 的集合的根为根的概率为 $n\over n+m$。
证明. 等价于 $n+m$ 个 rnd 值中，最大值是属于其中特定 $n$ 个点的概率，显然得证。
因此，可以得到：$E(h)\le \frac{n(h_n+2h_m)}{n+m}+\frac{m(2h_n+h_m)}{n+m}$
引理. $\forall x,f(x)\le x^2$
证明. 想证明 $f(t)\le t^2$，只需要证明对于任意 $n,m(n+m=t)$，如果最后一次合并的集合大小分别为 $n,m$，都有 $E(h)\le t^2$。不妨归纳证明
若已知 $f(n)\le n^2,f(m)\le m^2$，则带入上式得证：
\[E(h)\le n^2 +m^2+nm\le (n+m)^2=t^2\]根据琴升不等式：
\[2^{E(x)}\le E(2^x)\]因此：
\[2^{g(n)}\le f(n)\Rightarrow g(n)= O(\log n)\]作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: