poj3468线段树 区间加值 区间求和

题目传送 poj3468

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long//注意数据范围
const int maxn=2e5+5;
ll sum[maxn*3],a[maxn],lazy[maxn*3];
int N,q,b,c;
ll add,ans;/注意ans开全局的写法
char s[10];
void build(int l,int r,int root){//建树
    lazy[root]=0;
    if(l==r){
        sum[root]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,root<<1);//位运算乘2
    build(mid+1,r,root<<1|1);//偶数|1相当于该偶数加1
    sum[root]=sum[root*2]+sum[root*2+1];
}
void pushdown(int l,int r,int root){//延迟标记
    if(lazy[root]){
        lazy[root<<1]+=lazy[root];
        lazy[root<<1|1]+=lazy[root];
        int mid=(l+r)>>1;
        sum[root<<1]+=(mid-l+1)*lazy[root];
        sum[root<<1|1]+=(r-mid)*lazy[root];
        lazy[root]=0;//注意父节点懒标记还原为0
    }
}
void updt(int l,int r,int root){
    if(b<=l&&c>=r){
        sum[root]+=(r-l+1)*add;
        lazy[root]+=add;
        return ;
    }
    pushdown(l,r,root);
    int mid=(l+r)/2;
    if(b<=mid) updt(l,mid,root*2);
    if(c>=mid+1)updt(mid+1,r,root*2+1);
    sum[root]=sum[root*2]+sum[root*2+1];   
}
ll query(int l,int r,int root){
    if(b<=l&&c>=r)return ans+=sum[root];//全局写法的关键
    pushdown(l,r,root);
    int mid=(l+r)>>1;
    if(b<=mid)query(l,mid,root*2);
    if(c>=mid+1)query(mid+1,r,root*2+1);
    return ans;
}
int main(){
    scanf("%d%d",&N,&q);
    for(int i=1;i<=N;i++)
        scanf("%lld",&a[i]);
    build(1,N,1);
    for(int i=1;i<=q;i++){
        scanf("%s",s);
        if(s[0]=='Q'){
            ans=0;//ans要归零
            scanf("%d%d",&b,&c);            
            printf("%lld\n",query(1,N,1));
        }
        if(s[0]=='C'){
            scanf("%d%d%lld",&b,&c,&add);
            updt(1,N,1);            
        }
    }
    return 0;  
}