线段树的运用（例题）

　　A Simple Problem with Integers（poj3468）

文本翻译：

描述

你有n个整数，a1，a2，…的。你需要处理两种操作。一种类型的操作是在给定的间隔中给每个数字加上给定的数字。另一种是求给定区间内的数字之和。

输入

第一行包含两个数n和q 1，n，q小于100000。
第二行包含N个数，A1，A2，…的。- 1000000000±AI小于1000000000。
每个下一个Q行表示一个操作。
“C A B C”意味着将C添加到AA、AA + 1、…小于10000℃时，C＝10000。
“Q A B”意味着查询AA和AA + 1的总和，…Ab.

输出：

你需要按顺序回答所有Q命令。一个答案在一条线上。

样例：

输入

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

暗示

总和可能超过32位整数的范围。

#include<iostream>
#include<cstdio>

using namespace std;

int read(){
    char c;int sign=1;
    while((c=getchar())<'0'||c>'9')
        if(c=='-') sign=-1;
    int res=c-'0';
    while((c=getchar())<'0'||c<='9')
        res=res*10+c-'0';
    return res*sign;
} 

const int N=1e5+5;
int n,m,s[N];
int mi[N*4];
long long sum[N*4];

void build(int Lchild,int Rchild,int k){
//L,Rchild是指左右儿子；
    int mid=(Lchild+Rchild)/2;//二分建树 
    if(Lchild==Rchild){
        sum[k]=s[1];
        return  ;
    }
    build(Lchild,mid,k*2);//建立左子树； 
    build(mid+1,Rchild,k*2+1);//建立右子树；
    sum[k]=sum[k<<1]+sum[k<<1|1];//位运算优化常数 
}

void add(int k,int l,int r,int v){//给区间[l,r]所有的数加上v 
    mi[k]+=v;//打标记 
    sum[k]+=(r-l+1)*v;//维护对应的区间和 
    return;
}

void down(int k,int l,int r,int mid){//标记下传
    //判断
    if(mi[k]==0)//若无标记则不考虑此步操作 
        return ;//无需返回任何值 
    add(k*2,l,mid,mi[k]);// 下传到左子树 
    add(k*2+1,mid+1,r,mi[k]);//下传到右子树
    mi[k]=0;//标记清零 
}

long long query(int l,int r,int k,int x,int y){//查找
    if(l>=x&&r<=y)
        return sum[k];
    int mid=l+r>>1;
    long long res=0;
    down(k,l,r,mid);
    if(x<=mid)
        res+=query(l,mid,k<<1,x,y);
    if(mid<y)
        res+=query(mid+1,r,k<<1|1,x,y);
}

void modify(int k,int l,int r,int x,int y,int v){//给定区间[x,y]所有数加上v； 
    if(x<=l&&y>=r)
        return add(k,l,r,v);
    int mid=(l+r>>1);
    down(k,l,r,mid);//没达到一个节点都需要下传一次标记 
    if(x<=mid)
        modify(k*2,l,mid,x,y,v); //修改左子树 
    if(mid<y) 
        modify(k*2+1,mid+1,r,x,y,v);// 修改右子树 
        sum[k]=sum[k*2]+sum[k*2+1];//下传后更新sum的值 
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        s[i]=read();
    build(1,1,n);
    while(m--){
        char p;
        int A,B,C;
        while((p=getchar())!='Q'&&p!='C');//读入需要的字符Q或C
        A=read(),B=read(); 
        if(p=='Q')
            cout<<query(1,1,n,A,B)<<endl;
        else 
            modify(1,1,n,A,B,read());
    }
    return 0;
}