蒟蒻求调

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010;
int w[N],tr[4*N][4];
int n,M;

void pushup(int p){
    tr[p][0]=tr[p<<1][0]+tr[p<<1|1][0];
}

void pushdown(int p){
    if(tr[p][3]){
        tr[p<<1][0]+=tr[p][3]*(tr[p<<1][2]-tr[p<<1][1]+1);
        tr[p<<1|1][0]+=tr[p][3]*(tr[p<<1|1][2]-tr[p<<1|1][1]+1);
        tr[p<<1][3]+=tr[p][3];
        tr[p<<1|1][3]+=tr[p][3];
        tr[p][3]=0;
    }
}

void build(int x,int l,int r){
    tr[x][0]=w[l];
    tr[x][1]=l;
    tr[x][2]=r;
    if(l==r)
        return;
    int m=l+r>>1;
    build(x<<1,l,m);
    build(x<<1|1,m+1,r);
    pushup(x);
}

int update(int p,int x,int k){
    if(tr[p][1]==x&&tr[p][2]==x){
        tr[p][0]+=k;
        return tr[p][0];
    } 
    int m=tr[p][1]+tr[p][2]>>1;
    if(m>x) update(p<<1,x,k);
    else update(p<<1|1,x,k);
    return tr[p][0]=tr[p<<1][0]+tr[p<<1|1][0];
}

void update(int p,int x,int y,int k){
    if(x<=tr[p][1]&&tr[p][2]<=y){
        tr[p][0]+=k*(tr[p][2]-tr[p][1]+1);
        tr[p][3]+=k;
        return;
    }
    int m=tr[p][1]+tr[p][2]>>1;
    if(x<=m)update(p<<1,x,y,k);
    if(y>m)update(p<<1|1,x,y,k);
    pushup(p);
}

int query(int p,int x,int y){
    if(x<=tr[p][1]&&tr[p][2]<=y)
        return tr[p][0];
    int m=tr[p][1]+tr[p][2]>>1;
    pushdown(p);
    int res=0;
    if(x<=m)res+=query(p<<1,x,y);
    if(y>m)res+=query(p<<1|1,x,y);
    return res;
}

signed main(){
    cin>>n>>M;
    for(int i=1;i<=n;i++)cin>>w[i];
    build(1,1,n);
    while(M--){
        int t,x,y,k;
        cin>>t>>x>>y;
        if(t==2){
            cout<<query(1,x,y)<<'\n';
        }else{
            cin>>k;
            update(1,x,y,k);
        }
    }
    return 0;
}