首页 > 代码库 > HDU1166 敌兵布阵 树状数组水题

HDU1166 敌兵布阵 树状数组水题

中文题目,很简单的题目,区间求和,当然对于线段树来说也很水,为了练习一下树状数组,多做做水题吧,加深理解,并且打好基础,我算是被没打好基础给吓坏了,宁可多花几个小时 刷刷水题扎实点,

很裸的题目 操作也很裸,了解树状数组的肯定能做


#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

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

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::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;
}