hdu 1166 敌兵布阵

这题用了自顶向下的递归方式。
 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int MAXD = 50005;
 5 int tree[4*MAXD];
 6 int a[MAXD],D;
 7 int query(int x,int y)
 8 {
 9     int i=D+x-1, j=D+y+1, ans=0;
10     for(; i+1 != j; i>>=1,j>>=1)
11     {
12         if(~i & 1)
13             ans += tree[i^1];
14         if(j & 1)
15             ans += tree[j^1];
16     }
17     return ans;
18 }
19 void update(int n)
20 {
21     for(; n ^ 1; n >>= 1)
22         tree[n>>1] = tree[n]+tree[n^1];
23 }
24 int main()
25 {
26     int T,n,m,i,x,y;
27     char cmd[7];
28     cin>>T;
29     m = 1;
30     while(T--)
31     {
32         cin>>n;
33         for(i = 1; i <= n; i++)
34             cin>>a[i];
35         D = 1;
36         while(D < n+2)
37             D <<= 1;
38         memset(tree,0,sizeof(tree));
39         for(i = 1; i <= n; i++)
40             tree[D+i] = a[i];
41         for(i = D-1; i; i--)
42             tree[i] = tree[i<<1] + tree[i<<1|1];
43         cout<<"Case "<<m++<<":\n";
44         cin>>cmd;
45         while(cmd[0] != 'E')
46         {
47             cin>>x>>y;
48             if(cmd[0] == 'Q')
49                 cout<<query(x,y)<<endl;
50             else if(cmd[0] == 'A')
51             {
52                 tree[D+x] += y;
53                 update(D+x);
54             }
55             else if(cmd[0] == 'S')
56             {
57                 tree[D+x] -= y;
58                 update(D+x);
59             }
60             cin>>cmd;
61         }
62     }
63     return 0;
64 }