杭电OJ 1166（C++）

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
97
98
99
100
101
#include <cstdio>
#include <cstring>
const int MAXN = 50005;

int tree[MAXN << 2];
int num[MAXN];
char s[7];
int L, R, C; //L，R为修改的位置，C为修改数

//更新结点信息，rt是此结点在线段树中的索引
void pushup(int rt)
{
	//结点的值等于其左子树的值加上右子树的值
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

//建立线段树
void build_tree(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (l == r) //此结点是叶子结点
	{
		tree[rt] = num[l];
		return;
	}
	int m = (l + r) >> 1;
	build_tree(l, m, rt << 1); //构造左子树
	build_tree(m + 1, r, rt << 1 | 1); //构造右子树
	pushup(rt);
}

//修改单点信息
void update(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (l == r) //叶子结点
	{
		tree[rt] += C;
		if (tree[rt] < 0) //防止减成负数
			tree[rt] = 0;
		return;
	}
	int m = (l + r) >> 1;
	if (L <= m) //在左子树中查找
		update(l, m, rt << 1);
	else //在右子树中查找
		update(m + 1, r, rt << 1 | 1);
	pushup(rt);
}

//区间查询
int query(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (L <= l && R >= r) //此区间被完全包含在目标区间中，返回此区间的值
		return tree[rt];
	int sum = 0;
	int m = (l + r) >> 1;
	if (L <= m) //此区间的左子树和目标区间有交集，搜索左子树
		sum += query(l, m, rt << 1);
	if (m < R) //此区间的右子树和目标区间有交集，搜索右子树
		sum += query(m + 1, r, rt << 1 | 1);
	return sum;
}

int main()
{
	int T;
	scanf("%d", &T);
	int n;
	memset(num, 0, sizeof(num));
	for (int Case = 1; Case <= T; Case++)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &num[i]);
		}
		printf("Case %d:n", Case);
		build_tree(1, n, 1);
		while (scanf("%s", s))
		{
			if (s[0] == 'E')
				break;
			else if (s[0] == 'Q') //线段树查询
			{
				scanf("%d%d", &L, &R);
				printf("%dn", query(1, n, 1));
			}
			else if (s[0] == 'A') //线段树点修改增加
			{
				scanf("%d%d", &L, &C);
				update(1, n, 1);
			}
			else if (s[0] == 'S') //线段树点修改减少
			{
				scanf("%d%d", &L, &C);
				C *= -1;
				update(1, n, 1);
			}
		}
	}
	return 0;
}