hdu1166树状数组

添加链接描述

#include<bits/stdc++.h>
using namespace std;
int t,n; 
int r,l;
const int maxn=51000;
int a[maxn];
int ai,aj;
void update(int i,int val){//更新节点值 
	while(i<=n){
		a[i]+=val;
		i+=(i&(-i));
	}
}
int sum(int i){//查询前缀和 
	int res=0;
	while(i>0){
		res+=a[i];
		i-=(i&(-i));
	}
	return res;
}
int main()
{
	int num=1;
	int x;
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			update(i,x);
		}
		printf("Case %d:\n",num);
		string str;
		while(cin>>str&&str!="End"){
			if(str[0]=='A'){
				scanf("%d%d",&ai,&aj);//ai表示第i个营地，aj表示操作数 
				update(ai,aj);
			}
			else if(str[0]=='S'){
				scanf("%d%d",&ai,&aj);//同上 
				update(ai,-aj);
			}
			else if(str[0]=='Q'){
				scanf("%d%d",&ai,&aj);//ai表示第i个营地，aj表示第j个营地，查询第i到j营地 
				printf("%d\n",sum(aj)-sum(ai-1));
			}
		}
		num++;
	}
	return 0;
}