可持久化平衡树

对于非均摊复杂度数据结构，可以通过可持久化保留所有历史版本，或者实现静态的操作（节点一经创建，就不会再被修改）。这里我们介绍可持久化平衡树。

由于 Splay 是均摊时间复杂度，因此不能可持久化。可持久化平衡树通常指可持久化 FHQ。

注意到 FHQ 的每次 split 和 merge 只会影响 \(O(\log n)\) 个节点的值。我们可以将所有受到影响的节点都拷贝一份，然后在副本上进行修改。时间 \(O(n\log n)\)，空间 \(O(n\log n)\)。

// 拷贝节点
int clone(int p) {
    if(!p) return 0;
    ++nn;
    sum[nn] = sum[p];
    val[nn] = val[p];
    sz[nn] = sz[p];
    pri[nn] = pri[p];
    tag_add[nn] = tag_add[p];
    tag_rev[nn] = tag_rev[p];
    tag_set[nn] = tag_set[p];
    chd[nn][0] = chd[p][0];
    chd[nn][1] = chd[p][1];
    return nn;
}

例题

P5055 【模板】可持久化文艺平衡树

题意

你需要维护一个序列，初始为空。实现 \(4\) 种操作：

• 单点插入；
• 单点删除；
• 区间翻转；
• 区间求和；

同时每一次操作都是基于某个历史版本，每次操作都会生成一个新的版本。查询操作则保持原版本不变。

注意到 merge(x, y) 所触及的节点（\(x\) 的右链，\(y\) 的左链）一定是 split() 复制出的新节点，因此 merge() 内无需复制节点。

split() 和 push_down() 大约会产生 \(2\) 倍空间常数，同时预留 FHQ 的复杂度波动范围 \(\log(n) \rightarrow 28\)，空间开 \(56\) 倍即可。

模板代码

#include<iostream>
#define ll long long
using namespace std;
const int N = 2E5 + 10;
const int M = N * 56;

ll sum[M];
int val[M], pri[M], sz[M], tag[M];
int chd[M][2], nn;

int rt[N];

int addNode(int v) {
    ++nn;
    val[nn] = sum[nn] = v;
    sz[nn] = 1;
    pri[nn] = rand();
    return nn;
}

int clone(int p) {
    if(!p) return 0;
    ++nn;
    val[nn] = val[p];
    sum[nn] = sum[p];
    sz[nn] = sz[p];
    tag[nn] = tag[p];
    pri[nn] = pri[p];
    chd[nn][0] = chd[p][0];
    chd[nn][1] = chd[p][1];
    return nn;
}

void push_up(int p) {
    sum[p] = sum[chd[p][0]] + sum[chd[p][1]] + val[p];
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void push_down(int p) {
    if(!tag[p]) return;
    tag[p] = 0;
    chd[p][0] = clone(chd[p][0]);
    chd[p][1] = clone(chd[p][1]);
    swap(chd[p][0], chd[p][1]);
    tag[chd[p][0]] ^= 1;
    tag[chd[p][1]] ^= 1;
}

void split(int p, int k, int &x, int &y) {
    if(!p) {
        if(k) throw -1;
        x = y = 0;
        return;
    }
    push_down(p);
    if(sz[chd[p][0]] + 1 <= k) {
        x = clone(p);
        split(chd[x][1], k - (sz[chd[p][0]] + 1), chd[x][1], y);
        push_up(x);
    } else {
        y = clone(p);
        split(chd[y][0], k, x, chd[y][0]);
        push_up(y);
    }
}

int merge(int x, int y) {
    if(!x || !y) return x | y;
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

void insert(int i, int p, int v) {
    int x, y;
    split(rt[i], p, x, y);
    rt[i] = merge(x, merge(addNode(v), y));
}

void del(int i, int p) {
    int x, y, z, w;
    split(rt[i], p - 1, x, w);
    split(w, 1, y, z);
    rt[i] = merge(x, z);
}

void rev(int i, int l, int r) {
    int x, y, z, w;
    split(rt[i], r, w, z);
    split(w, l - 1, x, y);
    tag[y] ^= 1;
    rt[i] = merge(x, merge(y, z));
}

ll query(int i, int l, int r) {
    int x, y, z, w;
    split(rt[i], r, w, z);
    split(w, l - 1, x, y);
    ll res = sum[y];
    rt[i] = merge(x, merge(y, z));
    return res;
}

int T;

int main() {

    srand(time(NULL));

    cin >> T;

    ll lst = 0;
    for(int i = 1; i <= T; i++) {
        ll ver, op, p, v, l, r;
        cin >> ver >> op;
        rt[i] = rt[ver];
        if(op == 1) {
            cin >> p >> v;
            p ^= lst, v ^= lst;
            insert(i, p, v);
        } else if(op == 2) {
            cin >> p;
            p ^= lst;
            del(i, p);
        } else if(op == 3) {
            cin >> l >> r;
            l ^= lst, r ^= lst;
            rev(i, l, r);
        } else {
            cin >> l >> r;
            l ^= lst, r ^= lst;
            lst = query(i, l, r);
            cout << lst << '\n';
        }
    }

    return 0;
}

P5350 P5586 序列

题意

有一个序列 \(a_n\) 和若干操作。

• \(\mathrm{1\ l \ r \ }\) 求 \(a_l\) 到 \(a_r\) 的和；
• \(\mathrm{2\ l \ r \ val \ }\) 将 \(a_l\) 到\(a_r\) 赋值为 \(\mathrm{val}\)；
• \(\mathrm{3\ l \ r \ val\ }\) 将 \(a_l\) 到 \(a_r\) 加上 \(\mathrm{val}\)；
• \(\mathrm{4\ l_1 \ r_1 \ l_2 \ r_2 }\) 将 \(a_{l_1}\) 到 \(a_{r_1}\) 复制到 \(a_{l_2}\) 到 \(a_{r_2}\) 处；
• \(\mathrm{5\ l_1 \ r_1 \ l_2 \ r_2 }\) 将 \(a_{l_1}\) 到 \(a_{r_1}\) 与 \(a_{l_2}\) 到 \(a_{r_2}\) 交换；
• \(\mathrm{6\ l \ r \ }\) 将 \(a_l\) 到 \(a_r\) 翻转；

输出所有操作 \(1\) 的答案，并在结束后输出最终的序列。

答案对 \(10^9+7\) 取模。保证操作数 \(\mathrm{val}\in[0,10^9+7)\)。

\(n,m\le 3\times 10^5\)

\(128\mathrm{MB}\)，\(3\mathrm{s}\)

注意到只有操作 \(4\) 和操作 \(5\) 是不平凡的。直接复制区间的根节点显然不可行。这是由于平衡树不是静态的，因此修改一个节点可能会影响到另一个位置的节点。

考虑使用可持久化平衡树实现静态操作。每次操作时都复制整条链，这样就不会影响到其它节点了。

\(128\mathrm{MB}\) 内存无法开下整个平衡树。考虑时间换空间，当空间满了之后就拍平重构，即可卡过空间。

代码

\(1.45\mathrm{s}\) / \(127.59\mathrm{MB}\)

#include<iostream>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
const int M = 3.63e6 + 10;
const int LIM = M - N;
const int MOD = 1e9 + 7;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

namespace io {

    char ch;
    inline void read(int &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
    }

    char buf[60], nc;
    inline void write(int x) {
        do {
            buf[++nc] = x % 10 + 48;
            x /= 10;
        } while(x);
        while(nc) putchar(buf[nc--]);
    }

}

using io::read;
using io::write;

int n, m;
int a[N];

int rt[N], nr;

int val[M], sum[M], sz[M], pri[M], tag_set[M], tag_rev[M], tag_add[M];
int chd[M][2], nn;

bool full;

inline int addNode(int v) {
    ++nn;
    if(nn > LIM) full = 1;
    sum[nn] = val[nn] = v;
    sz[nn] = 1;
    pri[nn] = rand();
    tag_rev[nn] = tag_add[nn] = chd[nn][0] = chd[nn][1] = 0;
    tag_set[nn] = -INF;
    return nn;
}

int clone(int p) {
    if(!p) return 0;
    ++nn;
    if(nn > LIM) full = 1;
    sum[nn] = sum[p];
    val[nn] = val[p];
    sz[nn] = sz[p];
    pri[nn] = pri[p];
    tag_add[nn] = tag_add[p];
    tag_rev[nn] = tag_rev[p];
    tag_set[nn] = tag_set[p];
    chd[nn][0] = chd[p][0];
    chd[nn][1] = chd[p][1];
    return nn;
}

void push_up(int p) {
    sum[p] = ((ll)sum[chd[p][0]] + sum[chd[p][1]] + val[p]) % MOD;
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void move_tag_set(int p, int v) {
    if(!p) return;
    tag_set[p] = v;
    tag_add[p] = 0;
    tag_rev[p] = 0;
    sum[p] = (ll)v * sz[p] % MOD;
    val[p] = v;
}

void move_tag_rev(int p) {
    if(!p) return;
    tag_rev[p] ^= 1;
}

void move_tag_add(int p, int v) {
    if(!p) return;
    if(tag_set[p] != -INF) (tag_set[p] += v) %= MOD;
    else (tag_add[p] += v) %= MOD;
    (sum[p] += (ll)v * sz[p] % MOD) %= MOD;
    (val[p] += v) %= MOD;
}

void push_down(int p) {
    if((tag_set[p] != -INF) || (tag_rev[p]) || (tag_add[p])) {
        chd[p][0] = clone(chd[p][0]);
        chd[p][1] = clone(chd[p][1]);
        if(tag_rev[p]) {
            swap(chd[p][0], chd[p][1]);
            move_tag_rev(chd[p][0]);
            move_tag_rev(chd[p][1]);
            tag_rev[p] = 0;
        }
        if(tag_set[p] != -INF) {
            move_tag_set(chd[p][0], tag_set[p]);
            move_tag_set(chd[p][1], tag_set[p]);
            tag_set[p] = -INF;
        }
        if(tag_add[p]) {
            move_tag_add(chd[p][0], tag_add[p]);
            move_tag_add(chd[p][1], tag_add[p]);
            tag_add[p] = 0;
        }
    }
}

void split(int p, int k, int &x, int &y) {
    if(k > sz[p]) throw -1;
    if(!p) {
        x = y = 0;
        return;
    }
    push_down(p);
    if(sz[chd[p][0]] + 1 <= k) {
        x = clone(p);
        split(chd[x][1], k - (sz[chd[p][0]] + 1), chd[x][1], y);
        push_up(x);
    } else {
        y = clone(p);
        split(chd[y][0], k, x, chd[y][0]);
        push_up(y);
    }
}

int merge(int x, int y) {
    if(!x || !y) return x | y;
    if(sz[x] > sz[y]) {
        x = clone(x);
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        y = clone(y);
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

void build(int &p, int l, int r) {
    if(l > r) return;
    int mid = (l + r) >> 1;
    p = addNode(a[mid]);
    if(l == r) {
        return;
    }
    build(chd[p][0], l, mid - 1);
    build(chd[p][1], mid + 1, r);
    push_up(p);
}
void flush(int p, int &cnt) {
    if(!p) return;
    push_down(p);
    flush(chd[p][0], cnt);
    a[++cnt] = val[p];
    flush(chd[p][1], cnt);
}
void build() {
    nn = 0;
    rt[nr = 0] = 0;
    build(rt[nr], 1, n);
}
void flush() {
    int tmp = 0;
    flush(rt[nr], tmp);
}

void split(int p, int l, int r, int &x, int &y, int &z) {
    int w;
    split(p, r, w, z);
    split(w, l - 1, x, y);
}

int merge(int x, int y, int z) {
    return merge(merge(x, y), z);
}

int query(int l, int r) {
    int x, y, z;
    split(rt[nr], l, r, x, y, z);
    int res = sum[y];
    rt[++nr] = merge(x, y, z);
    return res;
}

void set(int l, int r, int v) {
    int x, y, z;
    split(rt[nr], l, r, x, y, z);
    move_tag_set(y, v);
    rt[++nr] = merge(x, y, z);
}

void add(int l, int r, int v) {
    int x, y, z;
    split(rt[nr], l, r, x, y, z);
    move_tag_add(y, v);
    rt[++nr] = merge(x, y, z);
}

void rev(int l, int r) {
    int x, y, z;
    split(rt[nr], l, r, x, y, z);
    move_tag_rev(y);
    rt[++nr] = merge(x, y, z);
}

void copy(int l1, int r1, int l2, int r2) {
    bool flag = false;
    if(l1 > l2) {
        swap(l1, l2);
        swap(r1, r2);
        flag = true;
    }
    int x1, y1, z1, y2, z2, x, y;
    split(rt[nr], l2 - 1, x, y);
    split(x, l1, r1, x1, y1, z1);
    split(y, r2 - l2 + 1, y2, z2);
    if(flag) {
        y1 = y2;
    } else {
        y2 = y1
    }
    rt[++nr] = merge(merge(x1, y1, z1), merge(y2, z2));
}

void swap(int l1, int r1, int l2, int r2) {
    if(l1 > l2) {
        swap(l1, l2);
        swap(r1, r2);
    }
    int x1, y1, z1, y2, z2, x, y;
    split(rt[nr], l2 - 1, x, y);
    split(x, l1, r1, x1, y1, z1);
    split(y, r2 - l2 + 1, y2, z2);
    swap(y1, y2);
    rt[++nr] = merge(merge(x1, y1, z1), merge(y2, z2));
}

void print(int p) {
    if(!p) return;
    push_down(p);
    print(chd[p][0]);
    write(val[p]);
    putchar(' ');
    print(chd[p][1]);
}

int main() {

    srand(time(NULL));

    read(n), read(m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }

    build();

    while(m--) {
        int op;
        int l, r, l1, r1, l2, r2, val;
        read(op);
        if(op == 1) {
            read(l), read(r);
            cout << query(l, r) << '\n';
        } else if(op == 2) {
            read(l), read(r), read(val);
            set(l, r, val);
        } else if(op == 3) {
            read(l), read(r), read(val);
            add(l, r, val);
        } else if(op == 4) {
            read(l1), read(r1), read(l2), read(r2);
            copy(l1, r1, l2, r2);
        } else if(op == 5) {
            read(l1), read(r1), read(l2), read(r2);
            swap(l1, r1, l2, r2);
        } else if(op == 6) {
            read(l), read(r);
            rev(l, r);
        } else {
            print(rt[nr]);
            putchar('\n');
        }
        if(full) {
            flush();
            build();
            full = 0;
        }
    }

    print(rt[nr]);
    putchar('\n');

    return 0;
}