2016-08-22

HDU 1166 敌兵布阵【zkw线段树】

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=1166

题意：

单点更新，区间查询

分析：

zkw线段树基本姿势。
非递归线段树，利用完全二叉树数组存储的特点，自底向上遍历节点
ppt中的讲解：
http://www.slideshare.net/DanielChou/ss-7792670

代码：

/*************************************************************************
    > File Name: 1166.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/22 20:09:59
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int M;
int T[maxn << 2];
void build(int n)
{
	for(M = 1; M <= n + 1; M <<= 1);
	for(int i = M + 1; i <= M + n; i++) scanf("%d", &T[i]);
	for(int i = M - 1; i; i--){
		T[i] = T[i << 1] + T[i << 1 | 1];
	}
}
void add(int a, int x)
{
	T[a += M] += x;
	for(a >>= 1;a;a >>= 1){
		T[a] = T[a << 1] + T[a << 1|1];
	}
}
ll query(int l, int r)
{
	l = l + M - 1, r = r + M + 1;
	ll ans = 0;
	for(; l^r^1; l >>= 1, r >>= 1){
		if(~l & 1) ans += T[l ^ 1];
		if(r & 1) ans += T[r ^ 1];
	}
	return ans;
}
char s[10];
int main(void)
{	
	int kas; scanf("%d", &kas);
	for(int tt = 1; tt <= kas; tt++){
		int n;scanf("%d", &n);
		build(n);
		printf("Case %d:\n", tt);
		while(scanf("%s", s)){
			if(s[0] == 'E') break;
			int x, y;
			scanf("%d%d", &x, &y);
			if(s[0] == 'A') add(x, y);
			else if(s[0] == 'S') add(x, -y);
			else printf("%lld\n", query(x, y));
		}
	}
	return 0;
}