POJ 3468 A Simple Problem with Integers http://poj.org/problem?id=3468 树状数组维护区间加减，区间求和

POJ3468.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 100100;

char op[10];
int n, m, l, r;
long long x;
long long a[maxn], b[maxn], c[maxn];

struct FenwickTree {

	long long tree[maxn];

	void init(long long *a) {
		for (int i = 0; i < maxn; i++)
			tree[i] = a[i];
	}

	void add(int x, long long val) {
		for (int i = x; i < maxn; i += i & (-i))
			tree[i] += val;
	}

	long long sum(int x) {
		long long res = 0;
		for (int i = x; i > 0; i -= i & (-i))
			res += tree[i];
		return res;
	}
};

FenwickTree Bit1, Bit2;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i-1];
	}
	Bit1.init(b);
	Bit2.init(c);
	for (int cas = 1; cas <= m; cas++) {
		scanf("%s", op);
		if (op[0] == 'Q') {
			cin >> l >> r;
			long long res = a[r] - a[l-1];
			res += (r+1)*Bit1.sum(r) - l*Bit1.sum(l-1);
			res = res - Bit2.sum(r) + Bit2.sum(l-1);
			cout << res << endl;
		} else {
			cin >> l >> r >> x;
			Bit1.add(l, x);
			Bit1.add(r+1, -x);
			Bit2.add(l, x*l);
			Bit2.add(r+1, -(r+1)*x);
		}
	}
	return 0;
}