可参考P3372

#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int maxn = 100000;
struct ser_tree{
    int l, r;
    int mx, sum;
    int lazy;
} tr[maxn * 4];
int n, m;
int a[maxn];
int t, x, y, k;
void build(int id, int l, int r) // 建树
{
    tr[id].l = l;
    tr[id].r = r;
    if(l==r)
    {
        tr[id].sum = a[l];
        tr[id].mx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    tr[id].sum = tr[lid].sum + tr[rid].sum;
    tr[id].mx = max(tr[lid].mx, tr[rid].mx);
}
// void modify(int id, int x, int val) // 单点修改原数组的某个值
// {
//     if(tr[id].l==tr[id].r)
//     {
//         tr[id].sum = tr[id].mx = val;
//         return;
//     }
//     int mid = (tr[id].l + tr[id].r) >> 1;
//     modify(x < mid ? lid : rid, x, val);
//     tr[id].sum = tr[lid].sum + tr[rid].sum;
//     tr[id].mx = max(tr[lid].mx, tr[rid].mx);    
// }
void pushdown(int id)//下放标记
{
    if(tr[id].lazy && tr[id].l != tr[id].r) //如果下放到lazy不为0，并且不是叶子节点
    {
        tr[lid].lazy += tr[id].lazy; //左儿子lazy+父亲节点lazy
        tr[rid].lazy += tr[id].lazy; //右儿子lazy+父亲节点lazy                                   
        tr[lid].sum += tr[id].lazy * (tr[lid].r - tr[lid].l + 1);//左儿子的sum+父亲节点lazy*（左儿子的右节点-左儿子的左节点+1）（个数）
        tr[rid].sum += tr[id].lazy * (tr[rid].r - tr[rid].l + 1);
        tr[id].lazy = 0;//父亲节点的lazy清空
    }
}

int query(int id, int l, int r) // 查询区间和
{
    
    if(tr[id].l==l && tr[id].r==r)
        return tr[id].sum;
    pushdown(id);    
    int mid = (tr[id].l + tr[id].r) >> 1;
    if(r<=mid)
        return query(lid, l, r);
    if(l>mid)
        return query(rid, l, r);
    return query(lid, l, mid) + query(rid, mid + 1, r);
}

void add(int id, int l, int r, int val) // 区间修改
{
    if(l<=tr[id].l && r>=tr[id].r) // 匹配到后
    {
        tr[id].lazy += val;//lazy累计
        tr[id].sum += val * (tr[id].r - tr[id].l + 1);//sum更新
        return;
    }
    pushdown(id);
    int mid = (l + r) >> 1;//中点
    if(r<=mid)
        add(lid, l, r, val);//左儿子
    else
        if(l>mid)
            add(rid, l, r, val);//右儿子
        else
            add(lid, l, mid, val), add(rid, mid + 1, r, val);
    tr[id].sum = tr[lid].sum + tr[rid].sum;//pushup  回溯之前更新每个点的信息
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        cin >> t >> x >> y;
        if(t==1)
        {
            cin >> k;
            add(1, x, y, k);
        }
        else
            cout << query(1, x, y) << endl;
    }
    system("pause"); 
    return 0;
}