并查集问题
并查集
提个问题
存在若干个元素，$e_1,e_2,\ldots,e_n$。要求我们支持两种操作：
1.对于给定$i$与$j$，将$e_i$，$e_j$所在的两个集合合并为一个。
2.对于给定$i$与$j$，判断$e_i$，$e_j$是否处于同一个集合中
如果你将这些元素视作顶点，那么操作1实际是建立边$(e_i, e_j)$，而操作2是询问顶点$e_i$与顶点$e_j$是否连通。问题就转换为图论问题。
并查集是专门用于解决这两个问题的数据结构。
按秩合并
并查集的最简单的实现方式是维护一个森林。为每个元素建立一个结点，每个结点维护两个属性：father和rank。father表示父结点，而rank是以自己为根的子树的大小。
class Node{
Node father = this;
int rank = 1;
public Node getRoot(){
return father == this ? father : father.getRoot();
}
}
查询操作的结果可以通过判断两个元素所在树的根是否相同得到。
合并操作使用的是启发式合并，合并之前先找到两个结点所在树的根，并通过判断根是否相同判断两元素是否处于相同的集合中，如果是相同集合，就可以跳过合并。否则，则将较小集合的根的father字段设置为较大集合的根，并更新较大集合的根的rank字段。
Node union(Node a, Node b){
a = a.getRoot();
b = b.getRoot();
if(a == b){
return a;
}
if(a.rank >= b.rank){
b.father = a;
a.rank += b.rank;
return a;
}else{
a.father = b;
b.rank += a.rank;
return b;
}
}
由于这里使用的是启发式合并，每次只有较小的树会合并到较大的树中。而一个结点$u$与根的距离每扩大1，意味着它作为较小树中的成员合并到了较大的树中，而$u$所在的树的大小至少增大了一倍。由于$u$所在的树的大小最大为$n$，因此最多被合并$\log_2n$次，即$u$与根的距离最大为$\log_2n$。
因此查询和合并的时间复杂度均为$O(\log_2n)$。
路径压缩
可以看到按秩合并的主要时间费用都花在了getRoot()方法上，这个方法的时间复杂度为$O(\log_2n)$。那么我们能不能想个法子优化这个方法呢。
路径压缩就是一个好方法。首先father仅用来查询根结点，因此我们可以设置father为任何距离根结点更近的祖先结点，这样就可以减少每次查询花费的时间。其次需要重新定义秩，在按秩合并的情况下，秩代表的是子树的大小，但是在路径压缩技巧中，秩代表的是树的高度。
class Node{
Node father;
int rank;
public Node getRoot(){
return father.father == father ? father : (father = father.getRoot());
}
}
Node union(Node a, Node b){
a = a.getRoot();
b = b.getRoot();
if(a == b){
return a;
}
if(a.rank == b.rank){
a.rank++;
}
if(a.rank > b.rank){
b.father = a;
return a;
}else{
a.father = b;
return b;
}
}
这里getRoot()的时间复杂度会低于$O(\log_2n)$，事实上，你可以认为在你可以想象的任意大数据集中，它都是$O(1)$，这里并不给出证明，可以自行参考《算法导论》。
持久化
假如我们在原始的问题中再加上一个操作：
3.允许我们将并查集切换回到之前的某个版本。
这个问题就有点难度了。由于操作2是读操作，而操作1仅会修改两个结点的状态。因此假如我们用持久化结构保存每个结点的信息（father和rank），这样就可以同时实现版本的切换了。
但是注意如果我们使用路径压缩的技巧，可能一次操作会修改很多的结点（尽管摊还是$O(1)$），这就不适合使用持久化了。因此我们选择的优化技巧是按秩合并。
持久化结构可以使用持久化线段树或者持久化无旋Treap，它们的读写操作时间复杂度都为$O(\log_2n)$。因此在使用持久化结构作为底层的情况下，操作1、2的时间复杂度均为$O((\log_2n)^2)$，而操作3的时间复杂度为$O(1)$。