Hdu1166_敌兵布阵——线段树or树状数组

树状数组，插点问段

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=50000+5;
 6 int c[MAXN];
 7 int lowbit(int x)
 8 {
 9     return x&(-x);
10 }
11 int sum(int x)
12 {
13     int temp=0;
14     while(x>0){
15         temp+=c[x];
16         x-=lowbit(x);
17     }
18     return temp;
19 }
20 void update(int x,int num,int n)
21 {
22     while(x<=n){
23         c[x]+=num;
24         x+=lowbit(x);
25     }
26 }
27 int main()
28 {
29     int test;
30     scanf("%d",&test);
31     for(int cas=1;cas<=test;cas++){
32         printf("Case %d:
",cas);
33         int n;
34         scanf("%d",&n);
35         memset(c,0,sizeof(c));
36         int a;
37         for(int i=1;i<=n;i++){
38             scanf("%d",&a);
39             update(i,a,n);
40         }
41         char s[10];
42         int u,v;
43         loop:scanf("%s",&s);
44         if(s[0]=='A'){
45             scanf("%d%d",&u,&v);
46             update(u,v,n);
47             goto loop;
48         }
49         else if(s[0]=='S'){
50             scanf("%d%d",&u,&v);
51             update(u,-v,n);
52             goto loop;
53         }
54         else if(s[0]=='Q'){
55             scanf("%d%d",&u,&v);
56             printf("%d
",sum(v)-sum(u-1));
57             goto loop;
58         }
59         else
60             continue;
61     }
62     return 0;
63 }

View Code

线段树，单点修改

 1 #include<cstdio>
 2 #define lson l,m,rt<<1
 3 #define rson m+1,r,rt<<1|1
 4 const int maxn=50010;
 5 int sum[maxn<<2];
 6 void pushup(int rt)
 7 {
 8     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 9 }
10 void build(int l,int r,int rt)
11 {
12     if(l==r){
13         scanf("%d",&sum[rt]);
14         return ;
15     }
16     int m=(l+r)>>1;
17     build(lson);
18     build(rson);
19     pushup(rt);
20 }
21 void update(int p,int add,int l,int r,int rt)
22 {
23     if(l==r){
24         sum[rt]+=add;
25         return ;
26     }
27     int m=(l+r)>>1;
28     if(p<=m)
29         update(p,add,lson);
30     else
31         update(p,add,rson);
32     pushup(rt);
33 }
34 int query(int L,int R,int l,int r,int rt)
35 {
36     if(L<=l&&R>=r)
37         return sum[rt];
38     int m=(l+r)>>1;
39     int ret=0;
40     if(L<=m)
41         ret+=query(L,R,lson);
42     if(R>m)
43         ret+=query(L,R,rson);
44     return ret;
45 }
46 int main()
47 {
48     int test;
49     scanf("%d",&test);
50     for(int cas=1;cas<=test;cas++){
51         printf("Case %d:
",cas);
52         int n;
53         scanf("%d",&n);
54         build(1,n,1);
55         char s[10];
56         int i,j;
57         while(scanf("%s",&s)){
58             if(s[0]=='A'){
59                 scanf("%d%d",&i,&j);
60                 update(i,j,1,n,1);
61             }
62             else if(s[0]=='S'){
63                 scanf("%d%d",&i,&j);
64                 update(i,-j,1,n,1);
65             }
66             else if(s[0]=='Q'){
67                 scanf("%d%d",&i,&j);
68                 printf("%d
",query(i,j,1,n,1));
69             }
70             else if(s[0]=='E')
71                 break;
72         }
73     }
74     return 0;
75 }

View Code