HDU- 1166 敌兵布阵 - 线段树

Lily特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗?
Input
第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N (N<=50000)，表示Lily有N盆花。
接下来有N个正整数，第i个正整数ai (1<=ai<=50) 表示第i盆花的初始美观值。
接下来每行有一条命令，命令有4种形式：
（1）Add i j, i和j为正整数，表示第i盆花被照料的好，美观值增加j (j<=30)
（2）Sub i j, i和j为正整数，表示第i盆花被照料的不好，美观值减少j (j<=30)
（3）Query i j, i和j为正整数，i<=j，表示询问第i盆花到第j盆花的美观值之和
（4）End，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条
output:
对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

区间查询，单点修改

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

struct Tree {
	int left, right;
	int sum;
}t[4*N];

// 更新idx处的sum 
inline void pushup(int idx) { 
	t[idx].sum = t[idx << 1].sum + t[idx << 1 | 1].sum;
}

// 建树 
void build(int pos, int left, int right) {
	t[pos].left = left, t[pos].right = right;
	if (left == right) {
		t[pos].sum = a[left];
		return;
	}
	int mid = left + right >> 1;
	build(pos << 1, left, mid);
	build(pos << 1 | 1, mid + 1, right);
	
	pushup(pos);
}

// index处的值加value 
void change(int pos, int index, int value) {
	if (t[pos].left == t[pos].right) {
		t[pos].sum += value;
		return;
	}
	int mid = t[pos].left + t[pos].right >> 1;
	if (index <= mid) {
		change(pos << 1, index, value);
	} else {
		change(pos << 1 | 1, index, value);
	}
	
	pushup(pos);
}

// [left, right]区间内元素和 
int query(int pos, int left, int right) {
	if (t[pos].left >= left && t[pos].right <= right) {
		return t[pos].sum;
	}
	int mid = t[pos].left + t[pos].right >> 1;
	int tmp = 0;
	if (left <= mid) {
		tmp = query(pos << 1, left, right);
	}
	if (right > mid) {
		tmp += query(pos << 1 | 1, left, right);
	}
	return tmp;
}

int main() {
	int t = 0;
	cin >> t;
	for (int k = 1; k <= t; k ++) {

		scanf("%d", &n);
		for (int i = 1; i <= n; i ++) {
			scanf("%d", &a[i]);
		}
		build(1, 1, n);
		string s;
		printf("Case %d:\n", k);
		while(true) {
			cin >> s;
			if (s == "End") {
				break;
			}
			int a, b;
			cin >> a >> b;
			if (s == "Query") {
				int r = query(1, a, b);
				printf("%d\n", r);
			} else if (s == "Add") {
				change(1, a, b);
			} else {
				change(1, a, -b);
			}
		}
	}
	return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96