セグメントツリーセグメント更新テンプレート

#include <iostream>
#include <cstdio>

using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxx=100002;

struct{
    __int64 sum;
    int col;
}Tree[maxx<<2];

void pushUp(__int64 rt){
	Tree[rt].sum=Tree[rt<<1].sum+Tree[rt<<1|1].sum;
}

void build(int l,int r,int rt){
	Tree[rt].col=0;
	if(l==r){
		scanf("%I64d",&Tree[rt].sum);//   wa 
		return ;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	pushUp(rt);
}

void pushDown(int rt,int m){
	if(Tree[rt].col){
		Tree[rt<<1].col+=Tree[rt].col;// 
		Tree[rt<<1|1].col+=Tree[rt].col;
		Tree[rt<<1].sum+=(__int64)Tree[rt].col*(m-(m>>1));
		Tree[rt<<1|1].sum+=(__int64)Tree[rt].col*(m>>1);
		Tree[rt].col=0;
	}
}

void update(int L,int R,int c,int l,int r,int rt){
	if(L<=l && r<=R){
		Tree[rt].sum+=(r-l+1)*(__int64)c;
		Tree[rt].col+=c;
		return ;
	}
	pushDown(rt,r-l+1);
	int m=(l+r)>>1;
	if(L<=m)update(L,R,c,lson);
	if(R>m)update(L,R,c,rson);
	pushUp(rt);
}

__int64 query(int L,int R,int l,int r,int rt){
	if(L<=l && r<=R){
		return Tree[rt].sum;
	}
	pushDown(rt,r-l+1);
	int m=(l+r)>>1;
	__int64 ret=0;
	if(L<=m)ret+=query(L,R,lson);
	if(R>m)ret+=query(L,R,rson);
	return ret;
}

int main(){
	int n,o;
	scanf("%d%d",&n,&o);
	build(1,n,1);
	while(o--){
		char op[3];
		int x,y,c;
		scanf("%s",op);
		if(op[0]=='Q'){
			scanf("%d%d",&x,&y);
			printf("%I64d
",query(x,y,1,n,1));
		}else{
			scanf("%d%d%d",&x,&y,&c);
			update(x,y,c,1,n,1);
		}
	}
	return 0;
}

http://poj.org/problem?id=3468