线段树+懒标记求条

rt

#include<bits/stdc++.h>
#define int long long
#define N 100010
#define lc p<<1
#define rc p<<1|1
using namespace std;
struct lsx{
    int l,r,sam,add;
};
lsx a[N*4];
int n,m,w[N];
void build(int p,int x,int y){
    a[p].l=x;
    a[p].r=y;
    a[p].add=0;
    if(y==x){
        a[p].sam=w[x];
        return ;
    }
    int m=(x+y)>>1;
    build(lc,x,m);
    build(rc,m+1,y);
    a[p].sam=a[lc].sam+a[rc].sam;
    return ;
}
void pushdown(int p){
    if(a[p].add){
        a[lc].sam+=a[p].add*(a[lc].r-a[lc].l+1);
        a[rc].sam+=a[p].add*(a[rc].r-a[rc].l+1);
        a[lc].add+=a[p].add;
        a[rc].add+=a[p].add;
        a[p].add=0;
    }
}
void updata(int p,int x,int y,int k){
    if(x<=a[p].l&&a[p].r<=y){
        a[p].sam+=(a[p].r-a[p].l+1)*k;
        a[p].add+=k;
        return ;
    }
    int m=(a[p].l+a[p].r)>>1;
    pushdown(p);
    if(x<=m){
        updata(lc,x,y,k);
    }
    if(y>m){
        updata(rc,x,y,k);
    }
    a[p].sam=a[lc].sam+a[rc].sam;
    return ;
}
int re(int p,int x,int y){
    if(x<=a[p].l&&a[p].r<=y){
        return a[p].sam;
    }
    int m=(a[p].l+a[p].r)>>1;
    int sum=0;
    if(x<=m){
        sum+=re(lc,x,y);
    }
    if(y>m){
        sum+=re(rc,x,y);
    }
    return sum;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int q,x,y,k;
        cin>>q>>x>>y;
        if(q==1){
            cin>>k;
            updata(1,x,y,k);
        }else{
            cout<<re(1,x,y);
            puts("");
        }
    }
    return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
*/
//输出11 8 16