HDU 1166 敌兵布阵

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
线段树节点更新练习
第三棵线段树……TUT……
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXN = 50000 + 10;
 5 
 6 struct Node
 7 {
 8     int l, r;
 9     int sum;
10     Node *l_child, *r_child;
11 };
12 
13 int N;
14 int cnt;
15 Node Tree[ MAXN + MAXN ];
16 
17 void BuildTree( int l, int r, Node *Td )
18 {
19     Td -> l = l;
20     Td -> r = r;
21 
22     if ( l == r )
23     {
24         scanf( "%d", &Td->sum );
25         return;
26     }
27 
28     ++cnt;
29     Td-> l_child = Tree + cnt;
30     BuildTree( l, (l + r) / 2, Td -> l_child );
31 
32     ++cnt;
33     Td -> r_child = Tree + cnt;
34     BuildTree( (l + r) / 2 + 1, r, Td -> r_child );
35 
36     Td ->sum = Td -> l_child -> sum + Td -> r_child -> sum;
37 }
38 
39 void Update( int ii, int &e, Node *Td, char &op )
40 {
41     if ( ii == Td->l && ii == Td->r )
42     {
43         if ( op == 'S' ) Td -> sum -= e;
44         else Td -> sum += e;
45         return;
46     }
47 
48     int mid = ( Td->l + Td->r ) / 2;
49     if ( ii <= mid )
50          Update( ii, e, Td->l_child, op );
51     else if ( ii > mid )
52          Update( ii, e, Td->r_child, op );
53 
54     Td -> sum = Td -> l_child -> sum + Td -> r_child -> sum;
55     return;
56 }
57 
58 int Query( int l, int r, Node *Td )
59 {
60     if ( Td -> l == l && Td -> r == r ) return Td->sum;
61 
62     int mid = (Td->l + Td->r) / 2;
63 
64     if ( r <= mid ) return Query( l, r, Td->l_child );
65     else if ( l > mid ) return Query( l, r, Td->r_child );
66     else return Query( l, mid, Td -> l_child ) + Query( mid + 1, r, Td -> r_child );
67 }
68 
69 
70 int main()
71 {
72     int T, tt = 0;
73     char op[10];
74     scanf("%d", &T );
75     while ( T-- )
76     {
77         cnt = 0;
78         scanf( "%d", &N );
79         BuildTree( 1, N, Tree );
80         printf("Case %d:\n", ++tt );
81         while ( scanf( "%s", op ), op[0] != 'E' )
82         {
83             int a, b;
84             scanf( "%d%d", &a, &b );
85             switch( op[0] )
86             {
87                 case 'Q':
88                 printf( "%d\n", Query(a, b, Tree) );
89                 break;
90 
91                 case 'S':
92                 case 'A':
93                 Update( a, b, Tree, op[0] );
94                 break;
95             }
96         }
97     }
98     return 0;
99 }