动态开点线段树模板：区间加减、求区间和

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
struct Tree{
    int lson,rson;
    ll sum,lazy;
}tr[N * 2];
int root,idx;
ll a[N];
int n,m;
void pushup(int u){
    tr[u].sum = tr[tr[u].lson].sum + tr[tr[u].rson].sum;
}
void pushtag(int &p,int l,int r,int k){
    if(!p) p = ++ idx;
    tr[p].sum += (r - l + 1) * k;
    tr[p].lazy += k;
}
void pushdown(int u,int l,int r){
    if(tr[u].lazy == 0){
        return;
    }
    int mid = l + r >> 1;
    pushtag(tr[u].lson,l,mid,tr[u].lazy);
    pushtag(tr[u].rson,mid + 1,r,tr[u].lazy);
    tr[u].lazy = 0;
}
void build(int &p,int l,int r){
    if(!p) p = ++ idx;
    if(l == r){
        tr[p].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(tr[p].lson,l,mid);
    build(tr[p].rson,mid + 1,r);
    pushup(p);
}
void update(int &p,int l,int r,int ql,int qr,int k){
    if(!p) p = ++ idx;
    if(l >= ql && r <= qr){
        pushtag(p,l,r,k);
        return;
    }
    pushdown(p,l,r);
    int mid = l + r >> 1;
    if(ql <= mid) update(tr[p].lson,l,mid,ql,qr,k);
    if(qr > mid) update(tr[p].rson,mid + 1,r,ql,qr,k);
    pushup(p);
}
ll query(int p,int l,int r,int ql,int qr){
    if(l >= ql && r <= qr){
        return tr[p].sum;
    }
    pushdown(p,l,r);
    int mid = l + r >> 1;
    ll res = 0;
    if(ql <= mid) res = query(tr[p].lson,l,mid,ql,qr);
    if(qr > mid) res += query(tr[p].rson,mid + 1,r,ql,qr);
    pushup(p);
    return res;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        cin >> a[i];
    build(root,1,n);
    for(int i = 1;i <= m;i ++){
        int op,x,y,k;
        cin >> op;
        if(op == 1){
            cin >> x >> y >> k;
            update(root,1,n,x,y,k);
        }
        else{
            cin >> x >> y;
            cout << query(root,1,n,x,y) << endl;;
        }
    }
    return 0;
}