线段树(单点更新)/树状数组 HDOJ 1166 敌兵布阵

浏览数：17 / 时间：2015年06月08日

 1 /*
 2     线段树基本功能：区间值的和，修改某个值
 3 */
 4 #include <cstdio>
 5 #include <cstring>
 6 #define lson l, m, rt << 1
 7 #define rson m+1, r, rt << 1|1
 8 
 9 const int MAX_N = 50000 + 10;
10 int sum[MAX_N<<2];
11 
12 void pushup(int rt)            //杭电大牛：notOnlySuccess 版本
13 {
14     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
15 }
16 
17 void build(int l, int r, int rt)
18 {
19     if (l == r)
20     {
21         scanf ("%d", &sum[rt]);
22         return ;
23     }
24     int m = (l + r) >> 1;
25     build (lson);
26     build (rson);
27     pushup (rt);
28 }
29 
30 void update(int p, int add, int l, int r, int rt)
31 {
32     if (l == r)
33     {
34         sum[rt] += add;
35         return ;
36     }
37     int m = (l + r) >> 1;
38     if (p <= m)    update (p, add, lson);
39     else    update  (p, add, rson);
40     pushup (rt);
41 }
42 
43 int query(int ql, int qr, int l, int r, int rt)
44 {
45     if (ql <= l && r <= qr)
46     {
47         return sum[rt];
48     }
49     int m = (l + r) >> 1;
50     int ans = 0;
51     if (ql <= m)    ans += query (ql, qr, lson);
52     if (qr > m)        ans += query (ql, qr, rson);
53     
54     return ans;
55 }
56 
57 int main(void)            //HDOJ 1166 敌兵布阵
58 {
59     //freopen ("inA.txt", "r", stdin);
60     int t, n, cas, ans;
61     int b, c;
62     char s[10];
63     
64     while (~scanf ("%d", &t))
65     {
66         cas = 0;
67         while (t--)
68         {
69             scanf ("%d", &n);
70             build (1, n, 1);
71             printf ("Case %d:\n", ++cas);
72             while (~scanf ("%s", &s))
73             {
74                 if (strcmp (s, "End") == 0)    break;
75                 scanf ("%d%d", &b, &c);
76                 if (strcmp (s, "Query") == 0)
77                 {
78                     ans = query (b, c, 1, n, 1);
79                     printf ("%d\n", ans);
80                 }
81                 else if (strcmp (s, "Add") == 0)
82                 {
83                     update (b, c, 1, n, 1);
84                 }
85                 else if (strcmp (s, "Sub") == 0)
86                 {
87                     update (b, -c, 1, n, 1);
88                 }
89             }
90         }    
91     }
92     
93     return 0;
94 }

 1 /*
 2     树状数组
 3 */
 4 #include <cstdio>
 5 #include <cstring>
 6 
 7 const int MAX_N = 50000 + 10;
 8 int a[MAX_N];
 9 int n, num;
10 
11 int lowbit(int t)        //求 2^k
12 {
13     //return t & (t ^ (t - 1));
14     return t & (-t);
15 }
16 
17 void plus(int num, int x)        //第i个增加num个人
18 {
19     while (x <= n)
20     {
21         a[x] += num;
22         x += lowbit (x);
23     }
24 }
25 
26 int sum(int x)            //求前x项的和
27 {
28     int sum = 0;
29     while (x > 0)
30     {
31         sum += a[x];
32         x -= lowbit(x);
33     }
34     return sum;
35 }
36 
37 int main(void)
38 {
39     //freopen ("inA.txt", "r", stdin);
40 
41     int t;
42     char op[100];
43 
44     scanf ("%d", &t);
45     int k = t;
46 
47     while (k--)
48     {
49         memset (a, 0, sizeof (a));
50         scanf ("%d", &n);
51         for (int i=1; i<=n; ++i)
52         {
53             scanf ("%d", &num);
54             plus (num, i);
55         }
56         int r = 1;
57         while (scanf ("%s", &op), op[0] != ‘E‘)
58         {
59             int a, b;
60             scanf ("%d%d", &a, &b);
61             switch (op[0])
62             {
63                 case ‘A‘:
64                     plus (b, a);
65                     break;
66                 case ‘S‘:
67                     plus (-b, a);
68                     break;
69                 case ‘Q‘:
70                     if (r)
71                         printf ("Case %d:\n", t - k);
72                     r = 0;
73                     printf ("%d\n", sum (b) - sum (a-1));
74                     break;
75             }
76         }
77     }
78 
79     return 0;
80 }