243. 一个简单的整数问题2

图片说明

AC代码

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
const int mod = 1000000007;

int N,M;
int arr[maxn];
struct node{
    ll l,r;
    ll sum,add;
}tr[maxn*4];

void pushup(int u){
    tr[u].sum = tr[u*2].sum+tr[u*2+1].sum;
}
void pushdown(int u){
    node &fa = tr[u],&left = tr[u*2],&right = tr[u*2+1];
    if(fa.add){
        left.add += fa.add;
        left.sum += (left.r-left.l+1)*fa.add;
        right.add += fa.add;
        right.sum += (right.r-right.l+1)*fa.add;
        fa.add = 0;
    }

}
void build(int u,int l,int r){
    if(l==r) tr[u] = {l,r,arr[l],0};
    else{
        tr[u] = {l,r};
        int mid = l+r>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}
ll query(int u,int l,int r){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    else {
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        ll sum = 0;
        if(l<=mid) sum += query(u*2,l,r);
        if(r>mid) sum += query(u*2+1,l,r);
        pushup(u);
        return sum;
    }
}

void modify(int u,int l,int r,int d){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].sum += (tr[u].r-tr[u].l+1)*d;
        tr[u].add += d;
    }else{
        pushdown(u);
        int mid = tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u*2,l,r,d);
        if(r>mid) modify(u*2+1,l,r,d);
        pushup(u);
    }
}

int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
    build(1,1,N);
    char op[2];int a,b,d;
    while(M--){
        scanf("%s",op);
        if(*op == 'Q'){
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(1,a,b));
        }else{
            scanf("%d%d%d",&a,&b,&d);
            modify(1,a,b,d);
        }
    }

    return 0;
}