POJ-3468線分ツリー--区間加算テンプレート

これはセグメントツリー区間の和を求めるテンプレートで、後で直接copyで使用します.

#include 
#include 
#include 
#include 
#include 
#define siz 100005
#define LL __int64
using namespace std;
struct node{
    LL data,addMark;
};
node arr[siz*4];
LL p[siz];
int n,m;
void build(int root,int start,int ends){
     if(start==ends){
        arr[root].data=p[ends];
        arr[root].addMark=0;
        return ;
     }
     int mid=(start+ends)>>1;
     build(root<<1,start,mid);
     build((root<<1)+1,mid+1,ends);
     arr[root].data=arr[root<<1].data+arr[(root<<1)+1].data;
     arr[root].addMark=0;
}
void pushDown(int root,int m){
    if(arr[root].addMark!=0){
        arr[root*2].addMark+=arr[root].addMark;
        arr[root*2+1].addMark+=arr[root].addMark;
        arr[root*2].data+=(m-(m>>1))*arr[root].addMark;
        arr[root*2+1].data+=(m>>1)*arr[root].addMark;
        arr[root].addMark=0;
    }
}
LL query(int root,int s,int e,int start,int ends){
    if(s==start&&e==ends) return arr[root].data;
    pushDown(root,e-s+1);
    int mid=(s+e)/2;
    //printf("%d %d %d
",root,start,ends);
    if(ends<=mid) return query(root<<1,s,mid,start,ends);
    else if(start>mid) return query((root<<1)+1,mid+1,e,start,ends);
    else
    return query(root*2,s,mid,start,mid)+query(root*2+1,mid+1,e,mid+1,ends);
}
void updata(int root,int s,int e,int st,int ends,int va){
    if(st>e||s>ends) return ;
    if(st==s&&e==ends){
        arr[root].addMark+=va;
        arr[root].data+=(ends-st+1)*va;
        return ;
    }
    pushDown(root,e-s+1);
    int mid=(s+e)>>1;
    if(ends<=mid) updata(root<<1,s,mid,st,ends,va);
    else if(st>mid) updata((root<<1)+1,mid+1,e,st,ends,va);
    else{
        updata(root<<1,s,mid,st,mid,va);
        updata((root<<1)+1,mid+1,e,mid+1,ends,va);
    }
    arr[root].data=arr[root<<1].data+arr[(root<<1)+1].data;
}
void solve(){
    //int m;
    //scanf("%d",&m);

   for(int i=1;i<=m;i++){
        getchar();
        int a,b,v;
        char q;
        //printf("^^^%d^^^
",m);
        scanf("%c %d %d",&q,&a,&b);
        //printf("###%d###
",m);
        if(q=='C'){
            scanf("%d",&v);
            updata(1,1,n,a,b,v);
        }
        else{
           // printf("%d %d %d&&&&&&&&&
",a,b,m);
            printf("%I64d
",query(1,1,n,a,b));
        }
    }
    //printf(" %d.
",arr[1].data);
}
int main()
{

        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%I64d",&p[i]);
        build(1,1,n);
        //printf(" %d.
",arr[1].data);
       // printf("Case %d: The total value of the hook is",i);
        solve();
    return 0;
}