可持久化线段树

luckydrawbox · 2022-05-21 19:02:15 · 个人记录

宏定义

常量与变量

函数

代码

#define pl a[p].tl
#define pr a[p].tr
struct Persistable_Segment_Tree{
    int tot,root[N*20];
    struct Edge{
        int l,r,tl,tr;
        int val;
    }a[N*20];
    Persistable_Segment_Tree(){
        tot=0;
    }
    void build(int p,int l,int r){
        if(l){
            a[p=++tot].l=l;
            a[p].r=r;
        }
        if(a[p].l==a[p].r){
            a[p].val=0;
            return;
        }
        int mid=(a[p].l+a[p].r)>>1;
        pl=++tot;a[pl].l=a[p].l;a[pl].r=mid;
        pr=++tot;a[pr].l=mid+1;a[pr].r=a[p].r;
        build(pl,0,0);build(pr,0,0);
    }
    int change(int fp,int x,int v){
        int p=++tot;
        a[p]=a[fp];
        if(a[p].l==a[p].r){
            a[p].val=v;
            return p;
        }
        int mid=(a[p].l+a[p].r)>>1;
        if(x<=mid)
            pl=change(a[fp].tl,x,v);
        else
            pr=change(a[fp].tr,x,v);
        return p;
    }
    int ask(int p,int x){
        if(a[p].l==a[p].r)
            return a[p].val;
        int mid=(a[p].l+a[p].r)>>1;
        if(x<=mid)
            return ask(pl,x);
        else
            return ask(pr,x);
    }
}tree;