深夜闲谈可持久化(1)-可持久化并查集

可持久化并查集,名字听起来非常高大上,其实就是将并查集的数组可持久化。

所以可持久化并查集又称可持久化数组。

但是由于数组的可持久化实现如果使用链表的话,会非常难实现,而且还会爆时间复杂度。

这时我们可以将数组的结构改为树状的结构,同时借用主席树的思想,这时可持久化并查集就转化为了可持久化树的构造,这样的话每次对数组的修改就变成了在可持久化树结构上从根到叶节点的一次修改。

数组 可持久化树

但是由于可持久化并查集的特殊性,这使得可持久化树的构造发生了一些改变。

我们对于这个可持久化树结构只需要维护其左节点和右节点就好了。

同时对于叶节点开另外的数组记录其节点的和节点深度

由于该算法无法使用路径压缩优化,这里使用按秩合并的方式来保证复杂度。

按秩合并:在并查集时将深度小的树合并到深度大的树上的底层优化。其时间复杂度为

此处就不证明按秩合并的复杂度了。

因为按秩合并的复杂度是,同时还有在可持久化树结构上的,所以总复杂度

需要注意的是,如果两个深度相同的根节点合并的话,将会使总子树的深度+1。因为此时没法保证子树浅的节点并到子树深的节点上只能强制一个节点子树深度+1。(按秩合并的复杂度证明)。

Code: