你说得对，但是，需要撤销和持久化的时候随机秩并查集就会大显身手！
by fangzichang @ 2023-09-25 16:33:57
@[fangzichang](/user/678087) 你在说什么？
by optimize_2 @ 2023-09-25 16:40:30
@[optimize_2](/user/224978)
就是为每个点随机一个秩，按合并的时候根的秩大的做根，但是让小的做根也不是不行。
我们高贵的随机秩并查集常数小，不需修改，复杂度稳定 $O(\log n)$，还没有 lz 的问题。
建议以后碰到并查集就写随机秩。
by fangzichang @ 2023-09-25 17:10:22
@[fangzichang](/user/678087) 但是撤销和可持久化并查集也不要随机秩啊。
by optimize_2 @ 2023-09-25 19:32:25
@[optimize_2](/user/224978) 当然可以启发式或者按高度，不过肯定要牺牲常数的，像 lz 提出来那种问题也会有的。
但是随机秩甚至不用修改秩。
by fangzichang @ 2023-09-25 19:47:01
本质上没有区别吧。。。爱用哪个用哪个不就行了。。。
by yinhee @ 2023-09-25 21:55:51
@[fangzichang](/user/678087) 请问为啥随机秩的是稳定的logn啊
by mori_ @ 2023-10-10 23:42:46
@[mori_](/user/339311) 可以参考一下 Treap 的复杂度证明
by fangzichang @ 2023-10-11 07:43:40
@[fangzichang](/user/678087) OK 谢谢大神
by mori_ @ 2023-10-11 14:03:06
@[fangzichang](/user/678087) 挺香，虽然比按秩合并慢
by jr_linys @ 2024-05-24 20:05:57