poj 3468 A Simple Problem with Integers

可以用树状数组，线段树，分块做。代码是分块

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int n, m, uu, vv, ww, blc, bel[100005];
ll sum[100005], tag[100005], a[100005];
char ss[15];
ll query(int uu, int vv){
	int p=bel[uu], q=bel[vv];
	ll re=0;
	if(p==q){
		for(int i=uu; i<=vv; i++)	re += a[i];
		re += tag[p] * (vv - uu + 1);
	}
	else{
		for(int i=p+1; i<=q-1; i++)	re += sum[i];
		for(int i=uu; i<=bel[uu]*blc; i++)	re += a[i] + tag[p];
		for(int i=(bel[vv]-1)*blc+1; i<=vv; i++)	re += a[i] + tag[q];
	}
	return re;
}
void update(int uu, int vv, int ww){
	int p=bel[uu], q=bel[vv];
	if(p==q){
		for(int i=uu; i<=vv; i++)	a[i] += ww;
		sum[p] += ww * (vv - uu + 1);
	}
	else{
		for(int i=p+1; i<=q-1; i++){
			sum[i] += ww * blc;
			tag[i] += ww;
		}
		for(int i=uu; i<=bel[uu]*blc; i++)	a[i] += ww;
		sum[p] += ww * (bel[uu]*blc - uu + 1);
		for(int i=(bel[vv]-1)*blc+1; i<=vv; i++)	a[i] += ww;
		sum[q] += ww * (vv - (bel[vv]-1)*blc);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++)	scanf("%lld", &a[i]);
	blc = sqrt(n);
	for(int i=1; i<=n; i++){
		bel[i] = (i - 1) / blc + 1;
		sum[bel[i]] += a[i];
	}
	while(m--){
		scanf("%s", ss);
		if(ss[0]=='Q'){
			scanf("%d %d", &uu, &vv);
			printf("%lld
", query(uu, vv));
		}
		else{
			scanf("%d %d %d", &uu, &vv, &ww);
			update(uu, vv, ww);
		}
	}
	return 0;
}