模板一:区间增值,区间求和
模板题:hud1556 Color the ball
const int maxn=100010;
int a[maxn],tree[4*maxn],lazy[4*maxn];
void pushup(int o){
tree[o]=tree[o<<1]+tree[o<<1|1];
}
void build(int o,int l,int r){
lazy[o]=0;
if(l==r){
tree[o]=a[l];
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
void pushdown(int o,int l,int r){
if(lazy[o]==0) return;
lazy[o<<1]+=lazy[o];
lazy[o<<1|1]+=lazy[o];
int mid=(l+r)>>1;
tree[o<<1]+=lazy[o]*(mid-l+1);
tree[o<<1|1]+=lazy[o]*(r-mid);
lazy[o]=0;
}
void puttag(int o,int l,int r,int v){
lazy[o]+=v;
tree[o]+=v*(r-l+1);
}
void change(int o,int l,int r,int ql,int qr,int v){
if(ql<=l && r<=qr){
puttag(o,l,r,v);
return;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) change(o<<1,l,mid,ql,qr,v);
if(qr>mid) change(o<<1|1,mid+1,r,ql,qr,v);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return tree[o];
int mid=(l+r)>>1;
pushdown(o,l,r);
int ans=0;
if(ql<=mid) ans+=query(o<<1,l,mid,ql,qr);
if(qr>mid) ans+=query(o<<1|1,mid+1,r,ql,qr);
return ans;
}
模板二:区间替换,区间求和
模板题:hdu1698 Just a Hook
const int maxn=100010;
int a[maxn],tree[4*maxn],lazy[4*maxn];
void pushup(int o){
tree[o]=tree[o<<1]+tree[o<<1|1];
}
void build(int o,int l,int r){
lazy[o]=0;
if(l==r){
tree[o]=a[l];
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
void pushdown(int o,int l,int r){
if(lazy[o]==0) return;
lazy[o<<1]=lazy[o];
lazy[o<<1|1]=lazy[o];
int mid=(l+r)>>1;
tree[o<<1]=lazy[o]*(mid-l+1);
tree[o<<1|1]=lazy[o]*(r-mid);
lazy[o]=0;
}
void puttag(int o,int l,int r,int v){
lazy[o]=v;
tree[o]=v*(r-l+1);
}
void change(int o,int l,int r,int ql,int qr,int v){
if(ql<=l && r<=qr){
puttag(o,l,r,v);
return;
}
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) change(o<<1,l,mid,ql,qr,v);
if(qr>mid) change(o<<1|1,mid+1,r,ql,qr,v);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return tree[o];
int mid=(l+r)>>1;
pushdown(o,l,r);
int ans=0;
if(ql<=mid) ans+=query(o<<1,l,mid,ql,qr);
if(qr>mid) ans+=query(o<<1|1,mid+1,r,ql,qr);
return ans;
}