树状数组

发表于2020-08-29更新于2023-09-15字数统计600阅读时长6分
  • 递归版线段树常数略大，在数据结构优化DP，树套树，etc 时容易超时。
  • 下为树状数组区间 / 单点增值，区间/单点查询模板 ( O(n)O(n) 建树)。
Binary Indexed Trees
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
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int MAXN = 1e5 + 5;

int n, m;

struct BIT { //Binary Index Trees, 1based
    int lowbit(int x) { return x & (~x + 1); }
    /* O(n) 建树*/
    void build(int x = 2, int sub = 1) {
        while (x <= n) {
            for (int i = x; i <= n; i += x)
                c[i] += c[i - sub];  //加上儿i - sub子的c
            x <<= 1, sub <<= 1;      // 2 ^ n
        }
    }
    /*@param x the position to add val*/
    void add(int x, LL val) {
        while (x <= n) c[x] += val, x += lowbit(x);
    }
    /*查询 [1, x] 的前缀和*/
    LL query(int x, LL res = 0) {
        while (x) res += c[x], x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
    res -= bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
    return res;
}

int main () {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> bit[0].c[i];
    bit[0].build();
    while (m--) {
        char opt;
        cin >> opt;
        if (opt == 'Q') {
            int x;
            cin >> x;
            cout << query(x, x) << "\n";
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            add(l, r, x);
        }
    }
    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
template <int MAXN>
struct BIT {
    struct Bit {
        int lowbit(int x) { return x & (-x); }

        void build(int x = 2, int sub = 1) {
            while (x <= n) {
                for (int i = x; i <= n; i += x)
                    c[i] += c[i - sub];  //加上儿i - sub子的c
                x <<= 1, sub <<= 1;      // 2 ^ n
            }
        }

        void add(int x, LL val) {
            while (x <= n) c[x] += val, x += lowbit(x);
        }

        LL query(int x, LL res = 0) {
            while (x) res += c[x], x -= lowbit(x);
            return res;
        }
        array<LL, MAXN> c;
    } bit[3];

    inline void add(int l, int r, LL val) {
        bit[1].add(l, val), bit[1].add(r + 1, -val);
        bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
    }

    inline LL query(int l, int r, LL res = 0) {
        res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
        res -=
            bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
        return res;
    }
};
BIT<MAXN> bit;