线段树

参考:线段树

模板题:线段树模板

写线段树需要注意的几点：

1. build和update的时候最后记得加和！（d[p]=d[p<<1]+d[p<<1|1]）
2. lazy标记下传后记得把父节点的清除！（laz[p]=0）

变量

const int maxn=1e5+5;
int d[maxn<<2],a[maxn],laz[maxn<<2];
    /*d[]保存区间和 a[]保存原始数据 laz[]懒惰标记为*/

建树

void build(int s,int t,int p)
{
    if(s==t)
    {
        d[p]=a[s];
        return ;
    }
    int m=(s+t)>>1;
    build(s,m,p<<1),build(m+1,t,p<<1|1);
    d[p]=d[p<<1]+d[p<<1|1];
}

下传懒惰标记

void pushdown(int s,int t,int p)
{
    int m=(s+t)>>1;
    d[p<<1]+=laz[p]*(m-s+1),d[p<<1|1]+=laz[p]*(t-m);
    laz[p<<1]+=laz[p],laz[p<<1|1]+=laz[p];
    laz[p]=0;
}

单点更新

void update(int x,int s,int t,int k,int p)
{
    if(s==t)
    {
        d[p]+=k;return ;
    }
    int m=(s+t)>>1;
    if(x<=m) update(x,s,m,k,lson);
    else update(x,m+1,t,k,rson);
    d[p]=d[lson]+d[rson];
}

区间更新

void update(int l,int r,int c,int s,int t,int p)
{
    if(l<=s&&t<=r)
    {
        d[p]+=(t-s+1)*c,laz[p]+=c;
        return ;
    }
    int m=(s+t)>>1;
    if(laz[p]) pushdown(s,t,p);
    if(l<=m) update(l,r,c,s,m,p<<1);
    if(r>m) update(l,r,c,m+1,t,p<<1|1);
    d[p]=d[p<<1]+d[p<<1|1];
}

区间求和

int getsum(int l,int r,int s,int t,int p)
{
    if(l<=s&&t<=r) return d[p];
    int m=(s+t)>>1;
    if(laz[p]) pushdown(s,t,p);
    int sum=0;
    if(l<=m) sum+=getsum(l,r,s,m,p<<1);
    if(r>m) sum+=getsum(l,r,m+1,t,p<<1|1);
    return sum;
}