HDOJ 1166 敌兵布阵 线段树： 单点更新 成段求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//HDOJ  1166  敌兵布阵   线段树： 单点更新 成段求和
/*
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1166

题意:  N个工兵营地（N<=50000），已知每个工兵营地的初始人数，
         Ｍ次（Ｍ<=40000）操作 : １、在第ｉ个营地增加ｊ个人；
	 		２、在第ｉ个营地减少ｊ个人；
       	 		３、询问营地ｉ到营地ｊ的总人数 ;
*/

#include<iostream>
using namespace std;

#define N 150005

struct node{
	int left;
	int right;
	int num;
};

node t[N];
int a[N];

int build(int r,int left,int right){
	t[r].left = left;
	t[r].right = right;
	if(left == right)
		return t[r].num = a[left];
	
	int m = (left + right) / 2;
	return t[r].num = build(r*2,left,m) + build(r*2+1,m+1,right);
}

int query(int r, int left, int right){
	int m = (t[r].left + t[r].right)/2;
	if((t[r].left == left) && (t[r].right == right))
		return t[r].num;
	if(right <= m)
		return query(r*2,left,right);
	if(left > m)
		return query(r*2+1,left,right);
	return query(r*2,left,m)+query(r*2+1,m+1,right);
}

void update(int r,int x,int y){
	t[r].num += y;
	if(t[r].left == t[r].right)
		return ;
	int m = (t[r].left + t[r].right)/2;
	if(x <= m)
		update(r*2,x,y);
	else
		update(r*2+1,x,y);
}

int main(){
	int i,j,T,n;
	int x,y;
	char s[5];
	scanf("%d",&T);
	for(i = 1; i <= T; ++i){
		scanf("%d",&n);
		for(j = 1; j <= n; ++j)
			scanf("%d",&a[j]);
		build(1,1,n);
		printf("Case %d:n",i);
		do{
			scanf("%s",s);
			if(s[0] == 'A'){
				scanf("%d %d",&x,&y);
				update(1,x,y);
			}
			else if(s[0] == 'S'){
				scanf("%d %d",&x,&y);
				update(1,x,-y);
			}
			else if(s[0] == 'Q'){
				scanf("%d %d",&x,&y);
				printf("%dn",query(1,x,y));
			}
		}while(s[0] != 'E');
	}
	return 0;
}