HDU 1166 敌兵布阵 树状数组例题

HDU 1166 敌兵布阵 树状数组题解

本题使用树状数组解决也是很好用的。

因为可以如果要求区间[a, b]的和，只记录从最小下标到b下标的和，然后减去最小下标到a-1的和，就得到区间和了

树状数组解决这类题目都很好用：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

class EnemyInfo_Tree_Arr_1
{
	static const int SIZE = 50005;
	int *tree;

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

	void update(int x, int val, int len)
	{//两边节点都需要更新？本题不需要
		while (x <= len)
		{
			tree[x] += val;
			x += lowbit(x);
		}
	}

	int query(int x)
	{
		int ans = 0;
		while (x > 0)
		{
			ans += tree[x];
			x -= lowbit(x);
		}
		return ans;
	}

public:
	EnemyInfo_Tree_Arr_1() : tree((int *)malloc(sizeof(int) * SIZE))
	{
		int T, N, a;
		char command[6];
		scanf("%d", &T);
		for (int t = 1; t <= T; t++)
		{
			printf("Case %d:\n",t);
			scanf("%d", &N);
			fill(tree, tree + N+1, 0);

			for (int i = 1; i <= N; i++)
			{
				scanf("%d", &a);
				update(i, a, N);
			}

			int b, c;
			while (scanf("%s", command) && command[0] != 'E')
			{
				scanf("%d %d", &b, &c);
				if (command[0] == 'Q')
					printf("%d\n", query(c) - query(b-1));
				else
				{
					if (command[0] == 'S') c = -c;
					update(b, c, N);
				}
			}
		}
	}
	~EnemyInfo_Tree_Arr_1()
	{
		free(tree);
	}
};