树状数组

数据结构与算法
字数统计: 255字   |   阅读时长≈ 1分钟

树状数组的总结

HDU - 1166 敌兵布阵

1
#include <bits/stdc++.h>
2
using namespace std;
3
int a[50005];
4
char cmd[1005];
5
int main()
6
{
7
    int t, n, m, i, j, k, ca = 1;
8
    scanf("%d", &t);
9
    while(t--)
10
    {
11
        scanf("%d", &n);
12
        for(i = 0; i <= n; i++)a[i] = 0;
13
        for(i = 1; i <= n; i++)
14
        {
15
            scanf("%d", &k);
16
            for(j = i; j <= n; j += j & -j)a[j] += k;
17
        }
18
        printf("Case %d:\n", ca++);
19
        while(scanf("%s", cmd) != EOF)
20
        {
21
            if(cmd[0] == 'E')break;
22
            else if(cmd[0] == 'Q')
23
            {
24
                int l, r;
25
                scanf("%d %d", &l, &r);
26
                int ans1 = 0, ans2 = 0;
27
                for(i = r; i > 0; i -= i & -i)ans1 += a[i];
28
                for(i = l - 1; i > 0; i -= i & -i)ans2 += a[i];
29
                printf("%d\n", ans1 - ans2);
30
            }
31
            else if(cmd[0] == 'A')
32
            {
33
                int x, y;
34
                scanf("%d %d", &x, &y);
35
                for(;x <= n; x += x & -x)a[x] += y;
36
            }
37
            else
38
            {
39
                int x, y;
40
                scanf("%d %d", &x, &y);
41
                for(;x <= n; x += x & -x)a[x] -= y;
42
            }
43
        }
44
    }
45
    return 0;
46
}
  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信