POJ 3468 A Simple Problem with Integers （线段树---区间更新）-蒲公英云

POJ 3468 A Simple Problem with Integers （线段树---区间更新）

A Simple Problem with Integers

Description

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c“ means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b“ means querying the sum of Aa, Aa+1, … , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

分析：线段树之区间更新，根据区间更新模板就可以很容易的写出来

AC代码：

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
LL sum[maxn<<2];
LL cnt[maxn<<2];  //延迟标记 
int N,Q;
void build(int l,int r,int rt){
    cnt[rt]=0;
    if(l==r){
      scanf("%lld",&sum[rt]);  //输入时注意lld，没注意到WA了一次 
      return ;    
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 
} 
void Down(int rt,int len){
   if(cnt[rt]){
       cnt[rt<<1]+=cnt[rt];
       cnt[rt<<1|1]+=cnt[rt];
       sum[rt<<1]+=cnt[rt]*(len-(len>>1));
       sum[rt<<1|1]+=cnt[rt]*(len>>1);
       cnt[rt]=0;
   }    
}
LL Query(int a,int b,int l,int r,int rt){
    if(a<=l && b>=r){
        return sum[rt];
    }
    Down(rt,r-l+1);
    int m=(l+r)>>1;
    LL ans=0;
    if(a<=m)
      ans+=Query(a,b,l,m,rt<<1);
    if(b>m)
      ans+=Query(a,b,m+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    return ans; 
}
void Update(int a,int b,int c,int l,int r,int rt){
    if(a<=l && b>=r){
        cnt[rt]+=c;
        sum[rt]+=(LL)(r-l+1)*c;
        return ;
    }
    Down(rt,r-l+1);
    int m=(r+l)>>1;
    if(a<=m)
     Update(a,b,c,l,m,rt<<1);
    if(b>m) 
     Update(a,b,c,m+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int main(){
    while(scanf("%d%d",&N,&Q)==2){
        build(1,N,1);
        for(int i=0;i<Q;i++){
            char ch;
            int a,b,c;
            getchar();
            scanf("%c",&ch);
            if(ch=='Q'){
                scanf("%d%d",&a,&b);
                LL ans=Query(a,b,1,N,1);
                printf("%lld\n",ans);
            }
            else {
                scanf("%d%d%d",&a,&b,&c); 
                Update(a,b,c,1,N,1);
            }
        }
    }
    return 0;
}