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
| #include <bits/stdc++.h>
#define MAXN 200005
#define lowbit(x) x&-x
using namespace std;
vector<int> v(MAXN), BIT(MAXN);
int n;
void build(){
int bit;
for(int i=1; i<=n; ++i){
bit = i;
while(bit <= n){
BIT[bit] += v[i];
bit += lowbit(bit);
}
}
}
void add(int pos, int val){
int ori = v[pos];
int diff = val - ori;
v[pos] = val;
while(pos <= n){
BIT[pos] += diff;
pos += lowbit(pos);
}
}
int sum(int x){
int total = 0;
while(x > 0){
total += BIT[x];
x -= lowbit(x);
}
return total;
}
int range_sum(int x, int y){
return (sum(y) - sum(x-1));
}
int main(){
int kase = 1;
char action[5];
while(scanf("%d", &n) && n){
BIT.assign(MAXN, 0);
if(kase > 1) puts("");
printf("Case %d:\n", kase);
for(int i=1; i<=n; ++i) scanf("%d", &v[i]);
build();
int x, y;
while(~scanf("%s", action) && action[0] != 'E'){
scanf("%d%d", &x, &y);
if(action[0] == 'S') add(x, y);
else if(action[0] == 'M') printf("%d\n", range_sum(x, y));
else printf("WTF\n");
}
++kase;
}
return 0;
}
|
