线段树求调

#include <iostream>
#define int long long
using namespace std;
const int size=1e5+10;
int a[size],sum[size*4],tag[size*4],bg[size*4],ed[size*4];
void build(int k,int beg,int end){
    bg[k]=beg,ed[k]=end,tag[k]=0;
    if(beg==end) sum[k]=a[beg];
    else{
        int mid=beg+(end-beg)/2;
        build(k*2,beg,mid),build(k*2+1,mid+1,end);
        sum[k]=sum[k*2]+sum[k*2+1];
    }
}
void pudn(int k){
    if(tag[k]==0) return;
    tag[k*2]+=tag[k],tag[k*2+1]+=tag[k],tag[k]=0;
    sum[k*2]+=tag[k*2]*(ed[k*2]-bg[k*2]+1),sum[k*2+1]+=tag[k*2+1]*(ed[k*2+1]-bg[k*2+1]+1);
}
int find(int k,int ql,int qr){
    if(ql<=bg[k]&&ed[k]<=qr) return sum[k];
    pudn(k);
    int r=0;
    if(ql<=ed[k*2]) r+=find(k*2,ql,qr);
    if(bg[k*2+1]<=qr) r+=find(k*2+1,ql,qr);
    return r;
}
void update(int k,int cl,int cr,int cv){
    if(cl<=bg[k]&&ed[k]<=cr) sum[k]+=cv*(ed[k]-bg[k]+1),tag[k]+=cv;
    else{
        pudn(k);
        if(cl<=ed[k*2]) update(k*2,cl,cr,cv);
        if(bg[k*2+1]<=cr) update(k*2+1,cl,cr,cv);
        sum[k]=sum[k*2]+sum[k*2+1];
    }
}

signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int o,x,y;
        cin>>o>>x>>y;
        if(o==1){
            int k;
            cin>>k;
            update(1,x,y,k);
        }else cout<<find(1,x,y)<<endl;
    }
    return 0;
}