基于带旋Treap的可持久化平衡树

Furioso_Slient · 2025-12-26 18:51:08 · 算法·理论

引入

没啥好引入的，我学了那么久的带旋 Treap，结果告诉我网上几乎找不到带旋的可持久化 Treap，怒了，因写本文。

注意：本文相关变量名含义如下：

变量名	含义
l_i,r_i	i 节点的左右子节点编号，不存在为 0
val_i	i 节点的权值
rnd_i	i 节点的随机权值
cnt_i	i 节点的出现次数（权值 val_i 的出现次数）
siz_i	i 节点及其子树一共包含的节点数
sz	节点数（最大节点）

可持久化

首先我们先简单唠唠什么是可持久化

知周所众，在做项目的时候，经常会出现：

“这个版本写的有亿点点 BUG 啊，你修改一下，不多，建议都准备好了，也就这个 256MB 的压缩包吧”
“啧啧，你这个呢，还是有点问题，依我拙见，这这这这（指出 114514 处地方）需要进行修改，你改一下”
“哎，咋都这么差呢？算了，还是第一版好，改回第一版吧”

此时不难注意到，如果你没有保存第一版的代码，你能被气到吐血。

所以可持久化就是类似于保存的一个机制：

保存历史版本
基于某一个历史版本进行修改或查询

同时，我们会发现如果每一次在保存历史版本时都完整的保存整个结构，显然会获得 MLE 的好成绩，所以可持久化数据结构的保存方式都是类似于差分保存的：仅保存修改的部分。

这件事放在线段树上和喝水一样简单：把发生修改的部分单独建立节点并指回原本的结构中，此时基于历史版本操作相当于对差分后的结构进行操作（也就是原本的那些点相当于不存在了）

但又知周所众的是，平衡树这个玩意它结构一改一变，相对于线段树而言，想要在这个上面实现可持久化的难度大的离谱，所以一般的可持久化平衡树均基于结构相对稳定的无旋 Treap （又称 FHQ-Treap）实现。

但带旋 Treap 的实现真的没有办法么？（包不可能的）

可行性

考虑每次 Treap 修改后的逻辑是什么。

我们偷一个带旋 Treap 的 insert 过来评鉴一下：

void insert(int &k,int x){
    if(!k){
        sz++;
        k=sz;
        siz[k]=1;
        cnt[k]=1;
        val[k]=x;
        rnd[k] = rand();
        return;
    }siz[k]++;
    if(val[k] == x){
        cnt[k]++;
    }else if(val[k]<x){
        insert(r[k],x);
    if(rnd[r[k]] < rnd[k])
        lrotate(k);//左旋
    }else{
        insert(l[k],x);
        if(rnd[l[k]] < rnd[k])
            rrotate(k);//右旋
    }
}

会发现每次插入点以后，从它的父亲一直到根的所有点均发生了旋转。

而旋转的操作是在将其父亲变成它的左（右）节点，将其左（右）子树挂在原本的父亲上。

如果我们每次遍历时认子不认父，发生状态改变的仅有被旋点和它的父亲。

所以我们可以直接将这些点直接复制后改变状态，然后用类似于主席树的处理方式，将新的节点指回原本的树中，然后存储下因为这一次状态操作所产生的新根即可。

同样，对于另一个会改变状态的删除而言，也可以使用这个方法解决。

对于查询，定然不会改变树的结构。

对于每次操作，都期望复制 O(\log n) 个节点。所以估算复杂度为：

单词时间复杂度：O(\log n)
总的空间复杂度：O(q\log n)

实现

我们首先实现一个函数，负责对节点进行复制：

我们新建一个节点，然后把需要复制的节点信息全部导入即可。

int copy(int k) {
    if (!k) return 0;
    ++sz;
    l[sz] = l[k]; r[sz] = r[k];
    val[sz] = val[k]; cnt[sz] = cnt[k];
    siz[sz] = siz[k]; rnd[sz] = rnd[k];
    return sz;
}

接下来考虑如何修改 insert 和 delete 函数。

对于每一次操作，如果我们想要改变这个点的状态，肯定需要对这个点进行复制，然后基于复制后的点进行修改。

我们先考虑容易实现的插入：

如果被插入点之前从未出现过，则直接插入即可。
如果被插入点之前出现过，就复制原本的点，在复制后的点上进行修改
如果该点不是被插入点，就对该点进行复制，然后基于被复制点的状态进行插入操作，回溯时以复制后的点进行旋转。

代码实现如下：

int insert(int k, int x) {
    if (!k){
        ++sz;
        l[sz] = r[sz] = 0;
        val[sz] = x;
        cnt[sz] = siz[sz] = 1;
        rnd[sz] = rand();
        return sz;
    }

    int nk = copy(k);//先复制
    siz[nk]++;

    if (val[nk] == x) {
        cnt[nk]++;//已存在，直接插入
    } else if (val[nk] < x) {
        r[nk] = insert(r[nk], x);//向下递归
        if (rnd[r[nk]] < rnd[nk]) lrotate(nk);//旋转维护
    } else {//同理
        l[nk] = insert(l[nk], x);
        if (rnd[l[nk]] < rnd[nk]) rrotate(nk);
    }
    return nk;
}

而对于删除，逻辑相同：

int del(int k, int x) {
    if (!k) return 0;

    int nk = copy(k);//先复制

    if (val[nk] == x) {
        if (cnt[nk] > 1) {//原本存在，直接删
            cnt[nk]--;
            siz[nk]--;
            return nk;
        }
        if (!l[nk] || !r[nk]) {//返回非空子节点继续递归
            return l[nk] | r[nk];
        }
        if (rnd[l[nk]] < rnd[r[nk]]) {
            l[nk] = copy(l[nk]);//复制
            rrotate(nk);//旋转，方便后续修改
            r[nk] = del(r[nk], x);//递归删除
        } else {//同理
            r[nk] = copy(r[nk]);
            lrotate(nk);
            l[nk] = del(l[nk], x);
        }
        upd(nk);//删除后点需要更新
        return nk;
    }

    if (val[nk] < x) {
        r[nk] = del(r[nk], x);
    } else {
        l[nk] = del(l[nk], x);
    }
    upd(nk);
    return nk;
}

验证

提交到【模板】可持久化平衡树后可以通过

const int N=5e5*50;
struct Treap {
    int l[N],r[N],val[N],cnt[N],siz[N],rnd[N];
    int sz=0;
    int newNode(int v) {
        ++sz;
        l[sz]=r[sz]=0;
        val[sz]=v;
        cnt[sz]=siz[sz]=1;
        rnd[sz]=rand();
        return sz;
    }
    int copy(int k) {
        if (!k) return 0;
        ++sz;
        l[sz]=l[k]; r[sz]=r[k];
        val[sz]=val[k]; cnt[sz]=cnt[k];
        siz[sz]=siz[k]; rnd[sz]=rnd[k];
        return sz;
    }

    void upd(int x) {
        if (x)
            siz[x]=siz[l[x]] + siz[r[x]] + cnt[x];
    }
    void lrotate(int &k) {
        int t=r[k];
        r[k]=l[t];
        l[t]=k;
        siz[t]=siz[k];
        upd(k);
        k=t;
    }

    void rrotate(int &k) {
        int t=l[k];
        l[k]=r[t];
        r[t]=k;
        siz[t]=siz[k];
        upd(k);
        k=t;
    }
    int insert(int k,int x) {
        if (!k){
            ++sz;
            l[sz]=r[sz]=0;
            val[sz]=v;
            cnt[sz]=siz[sz]=1;
            rnd[sz]=rand();
            return sz;
        }

        int nk=copy(k);
        siz[nk]++;

        if (val[nk] == x) {
            cnt[nk]++;
        } else if (val[nk] < x) {
            r[nk]=insert(r[nk],x);
            if (rnd[r[nk]] < rnd[nk]) lrotate(nk);
        } else {
            l[nk]=insert(l[nk],x);
            if (rnd[l[nk]] < rnd[nk]) rrotate(nk);
        }
        return nk;
    }
    int del(int k,int x) {
        if (!k) return 0;

        int nk=copy(k);

        if (val[nk] == x) {
            if (cnt[nk] > 1) {
                cnt[nk]--;
                siz[nk]--;
                return nk;
            }
            if (!l[nk] || !r[nk]) {
                return l[nk] | r[nk];
            }
            if (rnd[l[nk]] < rnd[r[nk]]) {
                l[nk]=copy(l[nk]);
                rrotate(nk);
                r[nk]=del(r[nk],x);
            } else {
                r[nk]=copy(r[nk]);
                lrotate(nk);
                l[nk]=del(l[nk],x);
            }
            upd(nk);
            return nk;
        }

        if (val[nk] < x) {
            r[nk]=del(r[nk],x);
        } else {
            l[nk]=del(l[nk],x);
        }
        upd(nk);
        return nk;
    }
    int queryrank(int k,int x) {
        if (!k) return 1;
        if (val[k] == x) return siz[l[k]] + 1;
        if (val[k] < x) return siz[l[k]] + cnt[k] + queryrank(r[k],x);
        return queryrank(l[k],x);
    }

    int querynum(int k,int x) {
        if (!k) return 0;
        if (x<=siz[l[k]]) return querynum(l[k],x);
        if (x > siz[l[k]] + cnt[k]) return querynum(r[k],x - siz[l[k]] - cnt[k]);
        return val[k];
    }

    int querypre(int k,int x) {
        if (!k) return -2147483647;
        if (val[k]>=x) return querypre(l[k],x);
        return max(val[k],querypre(r[k],x));
    }

    int querysub(int k,int x) {
        if (!k) return 2147483647;
        if (val[k]<=x) return querysub(r[k],x);
        return min(val[k],querysub(l[k],x));
    }
} T;

int root[500005];

void solve(){
    int q;
    cin>>q;
    srand(114514);

    int ver=0;
    root[0]=0;

    while(q--){
        int v,op,x;
        cin>>v>>op>>x;
        if(op == 1){
            root[++ver]=T.insert(root[v],x);
        }
        else if(op == 2){
            root[++ver]=T.del(root[v],x);
        }
        else if(op == 3){
            root[++ver]=root[v];
            cout<<T.queryrank(root[v],x)<<endl;
        }
        else if(op == 4){
            root[++ver]=root[v];
            cout<<T.querynum(root[v],x)<<endl;
        }
        else if(op == 5){
            root[++ver]=root[v];
            cout<<T.querypre(root[v],x)<<endl;
        }
        else{
            root[++ver]=root[v];
            cout<<T.querysub(root[v],x)<<endl;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

测试后，时间最慢 406ms，空间最差 234.81MB

后记

不到（

总之，带旋 Treap 万岁！！！

某些宣称只有无旋 Treap 才能持久化的言论是错误的。

当然，鼓励大家继续发掘神奇的持久化结构（~~可持久化 Splay、可持久化替罪羊树、可持久化 AVL 树~~）