HDU 1698

树状数组，板子题

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <deque>
using namespace std;

const int maxn= 50005;

int a[maxn];
string ord;
int n;

inline int LOWBIT(int i)
{
	return i & -i;
}
void Update(int x, int d)
{
	while (x<= n){
		a[x]+= d;
		x+= LOWBIT(x);
	}
}
int Sum(int x)
{
	int ret= 0;
	while (x> 0){
		ret+= a[x];
		x-= LOWBIT(x);
	}

	return ret;
}

int main(int argc, char const *argv[])
{
	int kase;
	int x, y;
	scanf("%d", &kase);
	for (int k_cnt= 1; k_cnt<= kase; ++k_cnt){
		scanf("%d", &n);
		for (int i= 1; i<= n; ++i){
			scanf("%d", a+i);
			int jb= LOWBIT(i);
			for (int j= 1; j< jb; j<<= 1){
				a[i]+= a[i-j];
			}
		}
		printf("Case %d:
", k_cnt);
		while (cin>>ord && 'E'!= ord[0]){
			scanf("%d %d", &x, &y);
			if ('A'== ord[0]){
				Update(x, y);
			}
			else if ('S'== ord[0]){
				Update(x, -y);
			}
			else{
				printf("%d
", Sum(y)-Sum(x-1));
			}
		}
	}
	return 0;
}