题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

思路

加lazy的线段树

#include 
#define maxn 1000000
#define max(x,y) x>y?x:y
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int k=0;
int pushdown(int p,int len)
{
    t[p<<1].lazy+=t[p].lazy;
    t[p<<1|1].lazy+=t[p].lazy;
    t[p<<1].x+=t[p].lazy*(len-len/2);
    t[p<<1|1].x+=t[p].lazy*(len/2);
    t[p].lazy=0;
}
int make(int p,int l,int r)
{
    int m=(l+r)>>1;
    if (l==r)
    {
        k++;
        t[p].x=a[k];
        return 0;
    }
    make(p<<1,l,m);
    make(p<<1|1,m+1,r);
    t[p].x=t[p<<1].x+t[p<<1|1].x;
}
int insert(int p,int l,int r,int x,int y,int k)
{
    int m=(l+r)>>1;
    if (x<=l&&y>=r)
    {
        t[p].lazy+=k;
        t[p].x+=(r-l+1)*k;
        return 0;
    }
    if (t[p].lazy)
        pushdown(p,r-l+1);
    if (y<=m) insert(p<<1,l,m,x,y,k);
    else if (x>m) insert(p<<1|1,m+1,r,x,y,k);
    else 
    {
        insert(p<<1,l,m,x,m,k);
        insert(p<<1|1,m+1,r,m+1,y,k);
    }
    t[p].x=t[p<<1].x+t[p<<1|1].x;
}
LL find(int p,int l,int r,int x,int y)
{
    int m=(l+r)>>1;
    if (x<=l&&y>=r)
        return t[p].x;
    if (t[p].lazy)
        pushdown(p,r-l+1);
    if (y<=m) return find(p<<1,l,m,x,y);
    else if (x>m) return find(p<<1|1,m+1,r,x,y);
    else return find(p<<1,l,m,x,m)+find(p<<1|1,m+1,r,m+1,y);
}
int main()
{
    int n=read(),m=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    make(1,1,n);
    for (int i=1;i<=m;i++)
    {
        int z=read(),x=read(),y=read();
        if (z==1)
        {
            int xx=read();
            insert(1,1,n,x,y,xx);
        }
        else printf("%lld\n",find(1,1,n,x,y));
    }
}