acwing算法提高之数据结构--树状数组

1 介绍

本专题用来记录树状数组相关题目。

树状数组：用来快速计算动态前缀和的数据结构。

 

树状数组支持两种操作：

1. 单点修改，比如a[i] += x
2. 区间查询，比如求a[l~r]的和

2 训练

题目1：241楼兰图腾

C++代码如下，

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];
int tr[N];
int Greater[N], lower[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; ++i) {
        int y = a[i];
        Greater[i] = sum(n) - sum(y);
        lower[i] = sum(y - 1);
        add(y, 1);
    }
    
    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; --i) {
        int y = a[i];
        res1 += Greater[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)(sum(y - 1));
        add(y, 1);
    }
    
    printf("%lld %lld\n", res1, res2);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

题目2：

3 参考

树状数组-OI WiKi