树状数组专题

说明

  • 支持单点更新及区间求和

代码模版

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
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repp(i,a,b) for(int i=b; i>=a; --i)
#define mp make_pair
#define pb push_back
#define ms(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int>vi;

const int maxn = 1e5+7;
int tree[maxn];
int lowbit(int x){
return x&(-x);
}
void update(int n, int inx, int add){
while(inx <= n){
tree[inx] += add;
inx += lowbit(inx);
}
}
int querySum(int e){
int sum = 0;
while( e>0 ){
sum += tree[e];
e -= lowbit(e);
}
return sum;
}
int queryLR(int left, int right){
return querySum(right)-querySum(left-1);
}
char op[10];
int main(){
int t, cas=0;
scanf("%d", &t);
while(t--){
ms(tree,0);
int n, a;
scanf("%d", &n);
rep(i, 1, n){
scanf("%d", &a);
update(n, i, a);
}
int x, y, z;
printf("Case %d:\n", ++cas);
while(scanf("%s", op), op[0]!='E'){
scanf("%d %d", &x, &y);
if(op[0] == 'A') update(n, x, y);
if(op[0] == 'S') update(n, x, -y);
if(op[0] == 'Q') printf("%d\n", queryLR(x, y));
}
}
return 0;
}