线段树模板【带懒标记】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
struct node{
    int l, r;
    ll add, sum;
    node(){
        add = sum = 0;
    }
}tr[N << 2];
void pushup(int u)
{
    tr[u].sum  = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    if(tr[u].add)
    {
        tr[u << 1].sum += tr[u].add * (ll)(tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].sum += tr[u].add * (ll)(tr[u << 1 | 1].r - tr[ u << 1 | 1].l +1);
        tr[u << 1].add += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add;
        tr[u].add = 0;
    }
}
void build(int u, int l, int r)
{
    tr[u].l = l,tr[u].r = r;
    if(l == r){
        tr[u].sum = a[r];
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int x, int l, int r)
{
    if(tr[u].l>=l && tr[u].r <= r)
    {
        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * x;
        tr[u].add += x;
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(mid >= l)
        modify(u << 1, x, l, r);
    if(mid < r)
        modify(u << 1 | 1, x, l, r);
    pushup(u);
}
ll query(int u, int l, int r)
{
    if(tr[u].l>=l && tr[u].r <=r)
        return tr[u].sum;
    //为什么要pushdown:如果tr[u].add > 0 ,那么说明u的子节点还没有更新过
    //pushdown能往下更新一层
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll sum = 0;
    if(mid >= l)
        sum = query(u << 1, l, r);
    if(mid < r)
        sum += query(u << 1 | 1, l, r);
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        char op[2];
        cin >> op;
        if(op[0] == 'C')
        {
            int l, r, d;
            cin >> l >> r >>d;
            modify(1, d, l, r);
        }
        else{
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}