数列的单点修改、区间求和
树状数组或线段树入门题
1 #include<stdio.h>
2 #include<string.h>
3
4 int c[50005],N;
5
6 void add(int x,int a){
7 while(x<=N){
8 c[x]+=a;
9 x+=(x&-x);
10 }
11 return;
12 }
13
14 int sum(int x){
15 int t=0;
16 while(x){
17 t+=c[x];
18 x-=(x&-x);
19 }
20 return t;
21 }
22
23 int main(){
24 int T;
25 while(scanf("%d",&T)!=EOF){
26 for(int q=1;q<=T;q++){
27 printf("Case %d:
",q);
28 memset(c,0,sizeof(c));
29 scanf("%d",&N);
30 int i,t;
31 for(i=1;i<=N;i++){
32 scanf("%d",&t);
33 add(i,t);
34 }
35 char s[10];
36 while(scanf("%s",s)){
37 // printf("%s
",s);
38 if(s[0]=='S'){
39 scanf("%d%d",&i,&t);
40 add(i,-t);
41 }
42 else if(s[0]=='A'){
43 scanf("%d%d",&i,&t);
44 add(i,t);
45 }
46 else if(s[0]=='Q'){
47 scanf("%d%d",&i,&t);
48 printf("%d
",sum(t)-sum(i-1));
49 }
50 else if(s[0]=='E')break;
51 }
52 }
53 }
54 return 0;
55 }
1 #include<stdio.h>
2 #include<string.h>
3 const int maxm=50005;
4
5 char s[10];
6 int a[maxm],st[maxm<<2];
7
8 void build(int o,int l,int r){
9 if(l==r){
10 st[o]=a[l];
11 return;
12 }
13 int m=l+((r-l)>>1);
14 build(o<<1,l,m);
15 build(o<<1|1,m+1,r);
16 st[o]=st[o<<1]+st[o<<1|1];
17 }
18
19 void update(int o,int l,int r,int x,int c){
20 if(l==r){
21 st[o]+=c;
22 return;
23 }
24 int m=l+((r-l)>>1);
25 if(x<=m)update(o<<1,l,m,x,c);
26 if(x>=m+1)update(o<<1|1,m+1,r,x,c);
27 st[o]=st[o<<1]+st[o<<1|1];
28 }
29
30 int query(int o,int l,int r,int ql,int qr){
31 if(ql<=l&&qr>=r)return st[o];
32 int m=l+((r-l)>>1);
33 int ans=0;
34 if(ql<=m)ans+=query(o<<1,l,m,ql,qr);
35 if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr);
36 return ans;
37 }
38
39 int read(){
40 int x=0;
41 char c=getchar();
42 while(c>'9'||c<'0')c=getchar();
43 while(c>='0'&&c<='9'){
44 x=x*10+c-'0';
45 c=getchar();
46 }
47 return x;
48 }
49
50
51 int main(){
52 int T=read();
53 for(int q=1;q<=T;q++){
54 int n=read();
55 int i;
56 for(i=1;i<=n;i++)a[i]=read();
57 build(1,1,n);
58 printf("Case %d:
",q);
59 while(1){
60 scanf("%s",s);
61 if(s[0]=='Q'){
62 int ql=read();
63 int qr=read();
64 printf("%d
",query(1,1,n,ql,qr));
65 }
66 else if(s[0]=='A'){
67 int x=read();
68 int c=read();
69 update(1,1,n,x,c);
70 }
71 else if(s[0]=='S'){
72 int x=read();
73 int c=read();
74 update(1,1,n,x,-c);
75 }
76 else if(s[0]=='E')break;
77 }
78 }
79 return 0;
80 }