动态开点线段树学习笔记

动态开点就是为了应付不同的版本的线段树,目前我只会具有单点修改的动态开店线段数,核心就是为每个版本分配一个root.一个版本是依据之前某一个版本修改过来的,而你只是单点修改的话,只会增加log(n)个节点,所以把父亲版本的数据先复制过来,然后再依据是否要修改左儿子和右儿子继续递归下去,在递归时返回新的段的标号,来更新父亲的左儿子右儿子数据,这样的话空间复杂度和时间夫再度都是O(nlog(n))

struct node{
     int sum,l,r;
}tr[N*30];
int rt[N];
int cnt=0;
void pushup(int p){
    tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum;
}
int build(int s,int t){
     int p=++cnt;
     if(s==t){
         return p;
     }
     int mid=(s+t)>>1;
     tr[p].l=build(s,mid);
     tr[p].r=build(mid+1,t);
     tr[p].sum=0;
     pushup(p);
     return p;
}
int update(int p,int s,int t,int l,int r,int x){
    int id=++cnt; 
    tr[id]=tr[p];
    if(l<=s&&t<=r){
        tr[id].sum=x;
        return id;
    }
    int mid=(s+t)>>1;
    if(l<=mid){
        tr[id].l=update(tr[id].l,s,mid,l,r,x);
    }
    if(mid+1<=r){
        tr[id].r=update(tr[id].r,mid+1,t,l,r,x);
    }
    pushup(id);
    return id;
}
int query(int p,int s,int t,int l,int r){
     if(l<=s&&t<=r){
         return tr[p].sum;
     }
     int ans=0;
     int mid=(s+t)>>1;
     if(l<=mid){
        ans+=query(tr[p].l,s,mid,l,r);
     }
     if(mid+1<=r){
        ans+=query(tr[p].r,mid+1,t,l,r);
     }
     return ans;
}