01trie 的合并与分裂

EnofTaiPeople · 2022-08-11 09:57:47 · 题解

Part 0：前言

01trie 将数字的二进制表示转化为字符插入到字典树，从而可以在树上二分，实现类似平衡树的查询功能，被称为常数、码量优秀，容易调试的平衡树，时空复杂度均为 O(n\log_2C)，C 为值域，以下均同。

本不想写题解，但可爱的 ydq 写了，于是就介绍一下,事实证明他没用 fread 码量还是比我大。

Part 1：01trie 的合并

合并的本质是对于两颗 trie 求和，过程如下：

若两棵树有一棵为空，返回非空的树；
否则，新建一个节点，大小为两树大小和（大小指叶子数量，下同）；
递归将左右儿子合并，接给新建节点；
返回新建节点。

代码实现（将 y 合并给 x）：

void Meg(int &x,int y,int w=W){
    if(!x||!y)return void(x|=y);
    sz[x]+=sz[y];
    if(w--){
        Meg(t[x][0],t[y][0],w);
        Meg(t[x][1],t[y][1],w);
    }
}

考虑分析时间复杂度，由于每一次同时拥有（即进入了第二步）的节点都会从两个减少到一个，而节点数是 O(n\log_2C) 的，所以总复杂度是 O(n\log_2C) 的。

Part 2：01trie 的分裂

分裂的本质是像 fhq 一样将一棵 01trie 按值域分为两棵 01trie，过程如下：

走到空子树，直接返回零；
考虑值域上这一位是否为一，将左子树全部分给左边或将右子树分给右边；
未被直接分配的一棵子树继续递归。

代码实现：

void Spt(int &x,int &y,int nod,int w=W){
    if(!nod)return void(x=y=0);
    if(w--){
        if((val>>w)&1){
            x=nod,y=++cnt,Spt(t[x][1],t[y][1],t[x][1],w);
        }else{
            y=nod,x=++cnt,Spt(t[x][0],t[y][0],t[y][0],w);
        }
        sz[x]=sz[t[x][0]]+sz[t[x][1]];
        sz[y]=sz[t[y][0]]+sz[t[y][1]];
    }else x=nod,y=0;
}

由于每次分裂只会增加 O(\log_2C) 个节点，所以是总复杂度 O(n\log_2C) 的。

而本题值域为 n，操作数为 m，所以总复杂度为 O((n+m)\log_2n)。

附上 AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,T=7e6+7,W=20;
char buf[N+5],*p1,*p2,c;
typedef long long ll;
#define int ll
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
    ll x,f=1;for(c=gc;c<48;c=gc)if(c=='-')f=-f;
    for(x=0;c>47;x=x*10+(48^c),c=gc);return x*f;
}
namespace trie_01{
    int t[T][2],cnt,val,dc;
    ll sz[T];
    void Ins(int &x,int w=W){
        if(!x)x=++cnt;sz[x]+=dc;
        if(w--)Ins(t[x][(val>>w)&1],w);
    }
    void Meg(int &x,int y,int w=W){
        if(!x||!y)return void(x|=y);
        sz[x]+=sz[y];
        if(w--){
            Meg(t[x][0],t[y][0],w);
            Meg(t[x][1],t[y][1],w);
        }
    }
    void Spt(int &x,int &y,int nod,int w=W){
        if(!nod)return void(x=y=0);
        if(w--){
            if((val>>w)&1){
                x=nod,y=++cnt,Spt(t[x][1],t[y][1],t[x][1],w);
            }else{
                y=nod,x=++cnt,Spt(t[x][0],t[y][0],t[y][0],w);
            }
            sz[x]=sz[t[x][0]]+sz[t[x][1]];
            sz[y]=sz[t[y][0]]+sz[t[y][1]];
        }else x=nod,y=0;
    }
    struct Trie{
        int rt;
        inline void insert(int x,int ct){
            val=x,dc=ct,Ins(rt);
        }
        inline void join(Trie &y){Meg(rt,y.rt);}
        inline int split(int l,int r){
            int L,R;val=l-1,Spt(L,rt,rt),val=r;
            Spt(rt,R,rt),Meg(L,R);swap(rt,L);return L;
        }
        inline ll rank(int d){
            int res=0,w=W,x=rt;
            while(w--)
                if((d>>w)&1)res+=sz[t[x][0]],x=t[x][1];
                else x=t[x][0];
            return res;
        }
        inline int gval(ll rk){
            if(rk<1||rk>sz[rt])return -1;
            int res=0,w=W,k,x=rt;
            while(w--){
                k=sz[t[x][0]];
                if(rk<=k)x=t[x][0];
                else rk-=k,x=t[x][1],res|=1<<w;
            }return res;
        }
    }tr[N];
} // namespace trie_01
using trie_01::tr;
ll n,q,cnt=1;
signed main(){
    ll op,x,l,r,k;
    n=read(),q=read();
    for(x=1;x<=n;++x)tr[1].insert(x,read());
    while(q--){
        op=read();
        switch(op){
            case 0:x=read(),l=read(),r=read(),tr[++cnt].rt=tr[x].split(l,r);break;
            case 1:x=read(),k=read(),tr[x].join(tr[k]);break;
            case 2:x=read(),k=read(),l=read(),tr[x].insert(l,k);
            break;
            case 3:x=read(),l=read(),r=read();
            printf("%lld\n",tr[x].rank(r+1)-tr[x].rank(l));break;
            case 4:x=read(),k=read();printf("%d\n",tr[x].gval(k));
            default:break;
        }
    }
    return 0;
}