可持久化并查集(Persistent Union-Find)

日付: 11月 03, 2018

## Operations
可持久化数据结构共有操作
* `new_ver(int t)` 从版本t生成一个新版本
* `query(int p, int t)` 查询版本t的状态
* `modify(int p, int t)` 在版本t的基础上修改

并查集特有操作
* `root(int x, int t)` 在版本t中，x所属的根
* `same(int x, int y, int t)` 在版本t中，x和y是否属于同一个集合
* `size(int x, int t)` 在版本t中，x所属集合的大小
* `unite(int x, int y, int t)` 在版本t中，将x和y所属的集合连接起来

这里t如果是负数表示倒数第t个版本

## Implementation
### Persistent
可持久化并查集实际上就是个可持久化数组，如果数据量较小可以用STL中的rope，其修改和查询的复杂度是$O(\sqrt n)$的。另一种方法是用可持久化线段树实现，只需要在叶子结点保存值。

### Union Find
* 因为每次修改都会产生$log(n)$个新结点，所以如果用路径压缩的话很可能导致爆空间

* 如果不用路径压缩，就必须要用启发式合并，小集合向大集合合并，这样可以保证深度是$log(n)$的，否则会超时

## Code
### Rope
```c++
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

struct PUnionFind {
    vector<rope<int>> F;
    PUnionFind(int n): F(1, rope<int>(n, -1)) {}

int get_ver(int t) { return t < 0 ? t + (int)F.size() : t; }
    void new_ver(int t = -1) { F.emplace_back(F[get_ver(t)]); }
    void modify(int p, int x, int t = -1) {
        if (t < 0) F.emplace_back(F.back());
        F[get_ver(t)].replace(p, x);
    }
    int query(int x, int t = -1) { return F[get_ver(t)].at(x); }
    int root(int x, int t = -1) { int p = query(x, t); return p < 0 ? x : root(p, t); }
    bool same(int x, int y, int t = -1) { return root(x, t) == root(y, t); }
    int size(int x, int t = -1) { return -query(x, t); }
    bool unite(int x, int y, int t = -1) {
        x = root(x, t), y = root(y, t);
        if (x != y) {
            int sx = size(x, t), sy = size(y, t);
            if (sx < sy) swap(x, y);
            modify(x, -sx - sy, t), modify(y, x, t);
        }
        return x != y;
    }
};
```

### Persistent Segment Tree
```c++
struct PUnionFind {
    const int n;
    vector<array<int, 2>> D;
    vector<int> V, R;
    PUnionFind(int n): n(n), D(n), V(n, -1), R(1, 1) {
        for (int i = n - 1; i; i--) D[i] = {i << 1, i << 1 | 1};
        for (auto &d : D) for (int i : {0, 1}) if (d[i] >= n) d[i] -= n;
    }

int get_ver(int t) { return t < 0 ? t + (int)R.size() : t; }
    void new_ver(int t = -1) { R.push_back(R[get_ver(t)]); }
    void modify(int p, int x, int t = -1) {
        int h = 30 - __builtin_clz(p += n), no = D.size(), tmp = no, o, i;
        assert(n <= p && p < n + n), D.resize((int)D.size() + h + 1);
        for (o = R[get_ver(t)]; h; ++no, --h)
            i = !!(1 << h & p), D[no] = D[o], D[no][i] = no + 1, o = D[o][i];
        D[no] = D[o], D[no][p & 1] = V.size(), V.push_back(x), R[get_ver(t)] = tmp;
    }
    int query(int p, int t = -1) {
        int o = R[get_ver(t)];
        for (int h = 30 - __builtin_clz(p += n); h >= 0; h--) o = D[o][!!(1 << h & p)];
        return V[o];
    }
    int root(int x, int t = -1) { int p = query(x, t); return p < 0 ? x : root(p, t); }
    bool same(int x, int y, int t = -1) { return root(x, t) == root(y, t); }
    int size(int x, int t = -1) { return -query(x, t); }
    bool unite(int x, int y, int t = -1) {
        x = root(x, t), y = root(y, t);
        if (x != y) {
            int sx = size(x, t), sy = size(y, t);
            if (sx < sy) swap(x, y);
            modify(x, -sx - sy, t), modify(y, x, t);
        }
        return x != y;
    }
};

```

KONGROOの基地

このブログを検索

可持久化并查集(Persistent Union-Find)

コメント

コメントを投稿