-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path敌兵布阵-线段树.cpp
141 lines (122 loc) · 3.17 KB
/
敌兵布阵-线段树.cpp
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<set>
#define INF 0x7fffffff
using namespace std;
const int maxn = 50000 + 10;
int n = 0;
char str[10];
struct SegTree{
int l,r; //记录每个节点的所表示的区间
int sum; //节点所表示区间的和
}stree[4 * maxn];
int arr[maxn];
void build(int root,int is,int ie){
stree[root].l = is;
stree[root].r = ie;
if(is == ie){ //叶子结点
stree[root].sum = arr[is];
return ;
}else{
//if(root == 2){
// cout << ie << " " << is << endl;
//}
int mid = (ie - is)/2 + is;
build(root*2,is,mid);
build(root*2+1,mid + 1,ie);
stree[root].sum = stree[root*2].sum + stree[root*2+1].sum;
}
}
void update_one(int root,int index,int add_val){
if(stree[root].l == stree[root].r){
if(stree[root].l == index){
//if(root == 8){
// cout << stree[root].l << " " << stree[root].r << endl;
// }
stree[root].sum += add_val;
}
return ;
}
int mid = (stree[root].r - stree[root].l)/2 + stree[root].l;
//stree[index].sum += add_val;
if(index <= mid){
update_one(root*2,index,add_val);
}else{
update_one(root*2+1,index,add_val);
}
stree[root].sum = stree[root*2].sum + stree[root*2+1].sum;
}
int query(int root,int qs,int qe){
//if(stree[root].l == stree[root].r && stree[root].l >= qs && stree[root].l <= qe){
//单点，并且该单点在所查找的区间，则返回值，否则不返回，之前就是在这里错了
// return stree[root].sum;
///}else
if(stree[root].l > qe || stree[root].r < qs){
//查询区间与当前区间没有交集时
return 0;
//}else if(stree[root].l == qs && stree[root].r == qe){
//查询区间与当前区间完全重合时
// return stree[root].sum;
}else if(qs <= stree[root].l && stree[root].r <= qe){
//当前区间包含在查询区间内
return stree[root].sum;
}else{ //当前区间部分包含在查询区间内
//int mid = (stree[root].r - stree[root].l)/2 + stree[root].l;
//return query(root*2,stree[root].l,mid) + query(root*2+1,mid+1,stree[root].r);
return query(root*2,qs,qe) + query(root*2+1,qs,qe);
}
/*
int mid = (stree[root].r - stree[root].l)/2 + stree[root].l;
if(stree[root].l == qs && stree[root].r == qe){
return stree[root].sum;
}
if(qs <= mid){
query(root*2,qs,qe);
}else if(mid > mid){
query(root*2+1,qs,qe);
}else{
return query(root*2,stree[root].l,mid) + query(root*2+1,mid+1,stree[root].r);
}
*/
}
int main(){
int T = 0,kase = 0,num = 0,loc = 0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d",&arr[i]);
}
build(1,1,n);
printf("Case %d:\n",++kase);
//for(int i = 0;i < 20;++i){
// cout << stree[i].sum << " ";
// }
// cout << endl;
while(true){
scanf("%s",str);//
if(str[0] == 'E'){
break;
}else{
scanf("%d %d",&loc,&num);
if(str[0] == 'Q'){
printf("%d\n",query(1,loc,num));
}else if(str[0] == 'A' ){
update_one(1,loc,num);
/*
for(int i = 0;i < 20;++i){
cout << stree[i].sum << " ";
}
cout << endl;
*/
}else if(str[0] == 'S'){
update_one(1,loc,-num);
}
}
}
}
return 0;
}