#include <stdio.h>
#include <stdlib.h>

#define MAX_N	100000

long long data_mul[MAX_N];
long long data_add[MAX_N];

void internal_update(int at, long long mul, long long add) {
	int i;
	for(i = at; i < MAX_N; i = (i | (i + 1))) {
		data_mul[i] += mul;
		data_add[i] += add;
	}
}

void update(int left, int right, long long it) {
	internal_update(left, it, -it * (left - 1));
	internal_update(right, -it, it * right);
}

long long query_sum(int x) {
	long long mul = 0, add = 0;
	int start = x;
	int i;
	for(i = x; i >= 0; i = (i & (i + 1)) - 1) {
		mul += data_mul[i];
		add += data_add[i];
	}
	return mul * start + add;
}

long long query(int x, int y) {
	return query_sum(y) - query_sum(x - 1);
}

int main(int argc, char *argv[]) {
	int N, Q;
	int i;
	long long l;
	int a, b;
	long long c;
	char cmd[2];
	scanf("%d %d", &N, &Q);
	for(i = 0; i < N; ++i) {
		scanf("%lld", &l);
		update(i, i, l);
	}
	while(Q--) {
		scanf("%s", cmd);
		if(cmd[0] == 'Q') {
			scanf("%d %d", &a, &b);
			printf("%lld\n", query(a - 1, b - 1));
		}
		else {
			scanf("%d %d %lld", &a, &b, &c);
			update(a - 1, b - 1, c);
		}
	}
	exit(0);
}

• Re:无耻的抄袭Fenwick Tree（树状数组）的代码 (290) Zenomyth 2013-09-03 11:35:10