原题链接：https://www.luogu.com.cn/problem/P3372

线段树

#include <iostream>

#define ll long long

const ll N = 1e6;
ll op[N];
struct ii{
    ll l;
    ll r;
    ll v;
    ll less;
}tree[N * 4];

void push_up(ll xx){
    tree[xx].v = tree[xx * 2].v + tree[xx * 2 + 1].v;
    return ;
}

void push_down(ll xx){
    tree[xx * 2].v += tree[xx].less * (tree[xx * 2].r - tree[xx * 2].l + 1);
    tree[xx * 2 + 1].v += tree[xx].less * (tree[xx * 2 + 1].r - tree[xx * 2 + 1].l + 1);
    tree[xx * 2].less += tree[xx].less;
    tree[xx * 2 + 1].less += tree[xx].less;
    tree[xx].less = 0;
}

void built(ll aa,ll bb,ll xx){
    if(aa == bb){
        tree[xx] = {aa,bb,op[aa]};
        return ;
    } else{
        tree[xx] = {aa,bb};
    }
    ll mid = (aa + bb) / 2;
    built(aa,mid,xx * 2);
    built(mid + 1,bb,xx * 2 + 1);
    push_up(xx);
    return ;
}

ll serch(ll aa,ll bb,ll xx){
    if(tree[xx].l >= aa && tree[xx].r <= bb){
        return tree[xx].v;
    }
    push_down(xx);
    ll res = 0;
    ll mid = (tree[xx].l + tree[xx].r) / 2;
    if(aa <= mid) res += serch(aa,bb,xx * 2);
    if(bb > mid) res += serch(aa,bb,xx * 2 + 1);
    return res;
}

void check(ll xx,ll aa,ll bb,ll cc){
    if(tree[xx].l >= aa && tree[xx].r <= bb){
        tree[xx].v += cc * (tree[xx].r - tree[xx].l + 1);
        tree[xx].less += cc;
        return ;
    }
    push_down(xx);
    ll mid = (tree[xx].l + tree[xx].r) / 2;
    if(aa <= mid) check(xx * 2,aa,bb,cc);
    if(bb > mid) check(xx * 2 + 1,aa,bb,cc);
    push_up(xx);
    return ;
}

void solve(){
    ll n,m;
    std::cin >> n >> m;
    for(ll i = 1; i <= n; i ++) std::cin >> op[i];
    built(1,n,1);
    while(m --){
        ll aa,bb,cc,dd;
        std::cin >> aa;
        if(aa == 1){
            std::cin >> bb >> cc >> dd;
            check(1,bb,cc,dd);
        } else{
            std::cin >> bb >> cc;
            std::cout << serch(bb,cc,1) << "\n";
        }
    }
}

int main(){
    ll t = 1;
    while(t --)
    solve();
    return 0;
}