HDU 1166 敌兵布阵 树状数组

单点更新，区间询问

//树状数组 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 5e4+5;

int a[maxn], c[maxn];
int T, n, x, k, cnt;
char s[10];

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

void update(int i, int k)
{
	while(i < maxn)
	{
		c[i] += k;
		i += lowbit(i);
	}
}

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

int main()
{
	scanf("%d", &T);
	cnt = 0;
	while(T--)
	{
		memset(c, 0, sizeof c);
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", a+i);
			update(i, a[i]);
		}
		printf("Case %d:\n", ++cnt);
		while(~scanf(" %s", s))
		{	
			//cout << s << endl;
			if(strcmp(s, "End") == 0) break;
			scanf("%d %d", &x, &k);
			if(strcmp(s, "Add") == 0)
			{
				update(x, k);
			}
			else if(strcmp(s, "Sub") == 0)
			{
				update(x, -k);
			}
			else if(strcmp(s, "Query") == 0)
			{
				printf("%d\n", getsum(k)-getsum(x-1));
			}
		} 
	}
	return 0;
 }

HDU 1166 敌兵布阵 树状数组

原文：https://www.cnblogs.com/hucorz/p/14346869.html