hdu1166敌兵布阵（线段树）

线段树单点更新
http://acm.hdu.edu.cn/showproblem.php?pid=1166
View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 int sum[1000001];
 4 void push(int w)
 5 {
 6     sum[w] = sum[2*w]+sum[2*w+1];//更新节点值
 7 }
 8 void build(int l,int r,int w)
 9 {
10     if(l==r)
11     {
12         scanf("%d",&sum[w]);
13         return;
14     }
15     int m = (l+r)/2;
16     build(l,m,2*w);
17     build(m+1,r,2*w+1);
18     push(w);
19 }
20 void add(int p,int d,int l,int r,int w)
21 {
22     if(l==r)
23     {
24         sum[w]+=d;
25         return ;
26     }
27     int m = (l+r)/2;
28     if(p<=m)
29         add(p,d,l,m,2*w);
30     else
31         add(p,d,m+1,r,2*w+1);
32     push(w);
33 }
34 int query(int p1,int p2,int l,int r,int w)
35 {
36     if(p1<=l&&p2>=r)//区间被完全覆盖
37         return sum[w];    
38     int m = (l+r)/2;
39     int re = 0;
40     if(p1<=m)
41         re+=query(p1,p2,l,m,2*w);
42     if(p2>m)
43         re+=query(p1,p2,m+1,r,2*w+1);
44     return re;
45 }
46 int main()
47 {
48     int i,j,k,n,t,a,b;
49     char c[11];
50     scanf("%d", &t);
51     for(i = 1; i <= t ; i++)
52     {
53         memset(sum,0,sizeof(sum));
54         scanf("%d", &n);
55         build(1,n,1);        
56         getchar();
57         printf("Case %d:\n",i);
58         while(scanf("%s",c)!=EOF)
59         {
60             if(strcmp(c,"End")==0)
61             break;
62             if(strcmp(c,"Add")==0)
63             {
64                 scanf("%d%d", &a,&b);
65                 add(a,b,1,n,1);
66             }
67             if(strcmp(c,"Sub")==0)
68             {
69                 scanf("%d%d", &a,&b);
70                 add(a,-b,1,n,1);
71             }
72             if(strcmp(c,"Query")==0)
73             {
74                 scanf("%d%d", &a,&b);            
75                 printf("%d\n",query(a,b,1,n,1));
76             }
77         }
78     }
79     return 0;
80 }