建树
void build(int l,int r,int rt)
{
if(l==r)
{
t[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,(rt<<1)|1);
t[rt]=t[rt<<1]+t[(rt<<1)|1];
}
标记下传
void pushdown(int l,int r,int rt)
{
if(lazy[rt])
{
int mid=(l+r)>>1;
lazy[rt<<1]+=lazy[rt];
lazy[(rt<<1)|1]+=lazy[rt];
t[rt<<1]+=lazy[rt]*(mid-l+1);
t[(rt<<1)|1]+=lazy[rt]*(r-mid);
lazy[rt]=0;
}
}
区间增加
void add(int l,int r,int L,int R,int rt,int x)
{
if(L<=l&&r<=R)
{
lazy[rt]+=x;
t[rt]+=(r-l+1)*x;
return;
}
pushdown(l,r,rt);
int mid=(l+r)>>1;
if(L<=mid)add(l,mid,L,R,rt<<1,x);
if(mid+1<=R)add(mid+1,r,L,R,(rt<<1)|1,x);
t[rt]=t[rt<<1]+t[(rt<<1)|1];
}
区间查询
int query(int l,int r,int L,int R,int rt)
{
if(L<=l&&r<=R)return t[rt];
int res=0;
pushdown(l,r,rt);
int mid=(l+r)>>1;
if(L<=mid)res+=query(l,mid,L,R,rt<<1);
if(mid+1<=R)res+=query(mid+1,r,L,R,(rt<<1)|1);
return res;
}