程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1166 敵兵布陣樹狀數組水題

HDU1166 敵兵布陣樹狀數組水題

編輯：C++入門知識

中文題目，很簡單的題目，區間求和，當然對於線段樹來說也很水，為了練習一下樹狀數組，多做做水題吧，加深理解，並且打好基礎，我算是被沒打好基礎給嚇壞了，寧可多花幾個小時刷刷水題扎實點，

很裸的題目操作也很裸，了解樹狀數組的肯定能做

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;


int n;
int c[100000 + 5];

void clear() {
	memset(c,0,sizeof(c));
}

int lowbit(int x) {
	return x&(-x);
}

void add(int i,int value) {
	while(i <= n) {
		c[i] += value;
		i += lowbit(i);
	}
}

int get_sum(int i) {
	int sum = 0;
	while(i > 0) {
		sum += c[i];
		i -= lowbit(i);
	}
	return sum ;
}

int main() {
	int t;
	int Case = 0;
	scanf("%d",&t);
	while(t--) {
		clear();
		scanf("%d",&n);
		printf("Case %d:\n",++Case);
		for(int i=1;i<=n;i++) {
			int x;
			scanf("%d",&x);
			add(i,x);
		}
		while(true) {
			char s[12];
			scanf("%s",s);
			if(s[0] == 'E') break;
			if(s[0] == 'A') {
				int x,y;
				scanf("%d %d",&x,&y);
				add(x,y);
			}
			else if(s[0] == 'S') {
				int x,y;
				scanf("%d %d",&x,&y);
				add(x,-y);
			}
			else {
				int x,y;
				scanf("%d %d",&x,&y);
				//int b = get_sum(y);
				//int a = get_sum(x - 1);
				int ans = get_sum(y) - get_sum(x - 1);
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}