线段树的合并与分裂

luckydrawbox · 2022-05-27 13:11:43 · 个人记录

宏定义

常量与变量

函数

代码

#define pl a[p].tl
#define pr a[p].tr
struct Segment_Tree{
    int tot,root[N],cnt,nc[N<<6];
    struct Tree{
        int tl,tr;
        ll val;
    }a[N<<6];
    Segment_Tree(){
        tot=0;
    }
    int get_new(){
        return cnt?nc[cnt--]:++tot;
    }
    void del(int p){
        nc[++cnt]=p;
        a[p].tl=a[p].tr=a[p].val=0;
    }
    void pushup(int p){
        a[p].val=a[pl].val+a[pr].val;
    }
    void add(int p,int x,int v,int L,int R){
        if(L==R){
            a[p].val+=v;
            return;
        }
        int mid=(L+R)>>1;
        if(x<=mid){
            if(!pl)
                pl=get_new();
            add(pl,x,v,L,mid);
        }
        else{
            if(!pr)
                pr=get_new();
            add(pr,x,v,mid+1,R);
        }
        pushup(p);
    }
    long long asksum(int p,int l,int r,int L,int R){
        if(l<=L&&R<=r)
            return a[p].val;
        int mid=(L+R)>>1;
        ll ans=0;
        if(!pl)
            pl=get_new();
        if(!pr)
            pr=get_new();
        if(l<=mid)
            ans+=asksum(pl,l,r,L,mid);
        if(r>mid)
            ans+=asksum(pr,l,r,mid+1,R);
        return ans;
    }
    int askkth(int p,int k,int L,int R){
        if(L==R)
            return L;
        int mid=(L+R)>>1;
        if(a[pl].val>=k)
            return askkth(pl,k,L,mid);
        else
            return askkth(pr,k-a[pl].val,mid+1,R);
    }
    int merge(int x,int y){
        if(!x||!y)
            return x+y;
        a[x].val+=a[y].val;
        a[x].tl=merge(a[x].tl,a[y].tl);
        a[x].tr=merge(a[x].tr,a[y].tr);
        del(y);
        return x;
    }
    void split(int p,int x,ll k){
        ll v=a[pl].val;
        if(k>v){
            a[x].tr=get_new();
            split(pr,a[x].tr,k-v);
        }
        else
            swap(pr,a[x].tr);
        if(k<v){
            a[x].tl=get_new();
            split(pl,a[x].tl,k);
        }
        a[x].val=a[p].val-k;
        a[p].val=k;
    }
}tree;