3468:A Simple Problem with Integers

問題文
http://poj.org/problem?id=3468

蟻本でも紹介されている問題。
セグメント木を実装した。各節点は次の2つのデータをもつ。
whole[ ] その節点の区間全体に一様に加えられた値
part[ ] その節点の区間に一様でなく加えられた値

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>
#define nmax (1<<18)

using namespace std;

typedef long long ll;

int n;
ll whole[nmax],part[nmax];

void add(int a,int b,int x,int k,int l,int r){
	
	if(a<=l && r<=b)whole[k]+=x;
	else if(l<b && a<r){
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
		part[k]+=(min(b,r)-max(a,l))*x;
	}
}

ll sum(int a,int b,int k,int l,int r){
	if(b<=l || r<=a)return 0;
	if(a<=l && r<=b)return (r-l)*whole[k]+part[k];
	else {
		ll vl=sum(a,b,k*2+1,l,(l+r)/2);
		ll vr=sum(a,b,k*2+2,(l+r)/2,r);
		return vl+vr+(min(b,r)-max(a,l))*whole[k];
	}
}

int main(void){
	
	int m;
	cin >> n >> m;
	
	for(int i=0;i<n;i++){
		int in;
		cin >> in;
		add(i,i+1,in,0,0,n);
	}
	
	for(int i=0;i<m;i++){
		int a,b,x;
		char c;
		scanf(" %c",&c);
		if(c=='Q'){
			scanf("%d %d",&a,&b);
			printf("%lld\n",sum(a-1,b,0,0,n));
		}
		else if(c=='C'){
			scanf("%d %d %d",&a,&b,&x);
			add(a-1,b,x,0,0,n);
		}
	}
	
	return 0;
}