c++ 懒标记线段树

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;
const int N=100005;
int n, m;
struct Node{
    int l, r;
    LL sum; // 存储总和
    LL tag; // 存储懒标记
}tr[N<<2];

inline void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}
inline void pushdown(int u){
    Node &root =tr[u];
    Node &left=tr[u<<1];
    Node &right=tr[u<<1|1];
    if(root.tag){
        left.tag+=root.tag;
        left.sum+=(LL)(left.r-left.l+1)*root.tag;
        right.tag+=root.tag;
        right.sum+=(LL)(right.r-right.l+1)*root.tag;
        root.tag=0; // 父节点懒标记分解
    }
}

void build(int u, int l, int r){
    tr[u]={l, r};
    if(l==r){scanf("%lld", &tr[u].sum); tr[u].tag=0; 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 l, int r, int d){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].tag+=d;
    }
    else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1, l, r, d);
        if(r>mid) modify(u<<1|1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    LL ans=0;
    if(l<=mid) ans+=query(u<<1, l, r);
    if(r>mid) ans+=query(u<<1|1, l, r);
    return ans;
}

int main(){
    cin>>n>>m;
    build(1, 1, n);
    char op[2];
    int l, r, d;
    while(m--){
        cin>>op>>l>>r;
        if(op[0]=='C'){
            cin>>d;
            modify(1, l, r, d);
        }
        else cout<<query(1, l, r)<<endl;
    }
    return 0;
}