HDU 1166(ツリー配列入門)

タイトルリンク:クリック
ACコード:

#include
#include
#include
#include
#define lowbit(i) ((i) & (-i)) 
using namespace std;
const int maxn = 100010;
int c[maxn];
int n, T;
int getSum(int x){
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i)){
		sum += c[i];
	}
	return sum;
}
void Add(int x, int v){
	for(int i = x; i <= n; i += lowbit(i)){
		c[i] += v;
	}
}
int main(){
	int k = 0;
	int x, y, v;
	cin >> T;
	while(T--){
		scanf("%d", &n);
		memset(c, 0, sizeof(c));
		for(int i = 1; i <= n; i ++){
			scanf("%d", &x);
			Add(i, x);
		}
		printf("Case %d:
", ++k);
		while(1){
			char s[10];
			scanf("%s", s);			 
			if(s[0] == 'A'){
				scanf("%d%d", &x, &v);
				Add(x, v);
			}else if(s[0] == 'Q'){
				scanf("%d%d", &x, &y);
				int ans = getSum(y) - getSum(x - 1);
				printf("%d
", ans);
			}else if(s[0] == 'S'){
				scanf("%d%d", &x, &v);
				Add(x, -v);
			}else {
				break;
			} 
		}
	}
	return 0;
}