线段树

参考：https://blog.csdn.net/zearot/article/details/48299459

模板：https://www.luogu.com.cn/problem/P3372

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m;
long long a[maxn];
long long sum[maxn*4],add[maxn*4];
void jianshu(int l,int r,int w)
{
    if(l==r)
    {
        sum[w]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    jianshu(l,mid,w*2);
    jianshu(mid+1,r,w*2+1);
    sum[w]=sum[w*2]+sum[w*2+1];
    return ;
}
int x,y;
long long k;
void pushdown(int w,int size1,int size2)
{
    add[w*2]+=add[w];
    add[w*2+1]+=add[w];
    sum[w*2]+=add[w]*size1;
    sum[w*2+1]+=add[w]*size2;
    add[w]=0;
    return ;
}
void jia(int l,int r,int w)
{
    if(l>=x&&r<=y)
    {
        sum[w]+=(r-l+1)*k;
        add[w]+=k;
        return ;
    }
    int mid=(l+r)/2;
    pushdown(w,mid-l+1,r-mid);
    if(x<=mid)
    {
        jia(l,mid,w*2);
    }
    if(mid<y)
    {
        jia(mid+1,r,w*2+1);
    }
    sum[w]=sum[w*2]+sum[w*2+1];
    return ;
}
long long ans=0;
void cha(int l,int r,int w)
{
    if(l>=x&&r<=y)
    {
        ans+=sum[w];
        return ;
    }
    int mid=(l+r)/2;
    pushdown(w,mid-l+1,r-mid);
    if(x<=mid)
    {
        cha(l,mid,w*2);
    }
    if(mid<y)
    {
        cha(mid+1,r,w*2+1);
    }
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    jianshu(1,n,1);
    while(m--)
    {
        int op;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            scanf("%lld",&k);
            jia(1,n,1);
        }
        else
        {
            ans=0;
            cha(1,n,1);
            printf("%lld\n",ans);
        }
    }
    return 0;
}