并查集

约 413 个字 22 行代码 预计阅读时间 2 分钟

以下为路径压缩时，各种情况的时间复杂度，表格摘自Tarjan论文

	朴素合并	按秩合并或者启发式合并
$m\ge n$	$m\log_{1+m/n}n$	$m\alpha(m,n)$
$m<n$	$n+m\log n$	$n+m\alpha(n,n)$

一般来说路径压缩+朴素合并就够用了

$\alpha(n)$ 为反阿克曼函数，当 $\alpha(n)=5,n\in[65536,2^{65536}]$

int f[MAXN],rk[MAXN];
void init(int n)
{
    memset(f,-1,sizeof(int)*(n+1));
    memset(rk,0,sizeof(int)*(n+1));
}
int find(int x)
{
    return f[x] == -1 ? x : (f[x] = find(f[x]));
}
void merge(int u, int v)
{
    int x = find(u), y = find(v);
    if(x==y)
        return;
    if (rk[x] <= rk[y])
        f[x] = y;
    else
        f[y] = x;
    if (rk[x] == rk[y] && x != y)
        rk[y]++;
}

朴素并查集维护的是可以简单传递的信息，亲戚的亲戚是亲戚。对于传递规则更复杂的信息，有种类并查集和带权并查集

种类并查集

敌人的敌人是朋友，开两倍空间，i和i+n是敌人，两个人有共同敌人，就是朋友

A吃B，B吃C，C吃A，i+n表示i的捕食对象，i+2n表示i的天敌

多开几倍空间，虚构和i是什么关系的对象，两个实体通过虚体联系在一起

带权并查集

在路径压缩和并集的时候，维护点和根之间的信息

已知(0,4],(2,4]的区间和，问给出的(0,2]区间和是否等于(0,4]区间和减(2,4]区间和

每次给出的区间若不在一个连通块，则并集，区间和作为非根点的点权；否则检查区间和是否合法（前缀和）

---

知道一部分同学的分数差，问另外一些同学的分数差

维护点和根的分数差，前缀和就可以回答询问

---

感觉就是动态加叶子的树上前缀和，只不过用并查集判断是加点还是询问