可持久化平衡树

FHQ Treap + 可持久化

普通FHQ Treap加上一点可持久化的东西如下：(打上注释的代码是可持久化的特殊操作)

int merge(int x, int y) {
    if(!x || !y) return x + y;
    if(t[x].key < t[y].key) {
        int rt = newnode(); //
        t[rt] = t[x];       //
        t[rt].s[1] = merge(t[rt].s[1], y);
        pushup(rt);
        return rt;
    } else {
        int rt = newnode(); //
        t[rt] = t[y];       //
        t[rt].s[0] = merge(x, t[rt].s[0]);
        pushup(rt);
        return rt;
    }
}
void split(int rt, int k, int &x, int &y) {
    if(!rt) x = y = 0;
    else {
        if(t[rt].w <= k) {
            x = newnode(); //
            t[x] = t[rt];  //
            split(t[x].s[1], k, t[x].s[1], y);
            pushup(x);
        } else {
            y = newnode(); //
            t[y] = t[rt];  //
            split(t[y].s[0], k, x, t[y].s[0]);
            pushup(y);
        } 
    }
}

然后开个root[]数组，存各个版本的根节点，然后注意下空间得开50倍。

其他可持久化扩展平衡树

可持久化要求是平衡树得用非旋来写（FHQ），所以其实会了上面的可持久化FHQ，变形也就简单了。

所以这里只是提一提：

• 可持久化文艺平衡树