常州集训Day3

看了昨天S组的PPT，讲的是线段树，手搓了一棵。
建树：

void build(int l,int r,int p){
    if(l==r){
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}

单点修改：

void undate1(int l,int r,int p,int pd,int d){
    if(l==r){
        tree[p]=d;
        return;
    }
    int mid=(l+r)>>1;
    if(pd<=mid)undate1(l,mid,p<<1,pd,d);
    else undate1(mid+1,r,p<<1|1,pd,d);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}

区间求和：

int query(int pl,int pr,int p,int l,int r,int res){
    int t=res;
    if(pl>=l&&pr>1;
    if(l<=mid)res+=query(pl,mid,p<mid)res+=query(mid+1,pr,p<<1|1,l,r,t);
    return res;
}