引入

需求

给定一个数组，有以下两个操作要实现

  1. query：能够计算前i个数的和；查询区间和
  2. update：支持单点更新

方案1：暴力法

  • query：用for循环求解，时间复杂度O(N)
  • update：直接赋值，时间复杂度O(1)

方案2：前缀和数组

  • query：用额外的空间存储，时间复杂度O(1)
  • update：赋值后，需要重新计算前缀和数组，时间复杂度O(N)

折中方案

  • Binary Indexed Tree和Segment Tree

  • 查找和修改时间复杂度均为O(logN)

  • Binary Indexed Tree：更少的空间，更易实现

  • Segment Tree：更大的使用范围

  • The BIT is specifically used for Dynamic - Cumulative stuffs, whereas the Segment tree is more general and can be used in all those situations where, the divide and conquer paradigm can be applied over queried interval.
  • All the jobs doable by BIT can essentially be done by segment tree but not vice-versa
  • 参考2：评论区

定义及实现

原理

  • 任意整数可以表示用二进制的位组合表示

Each integer can be represented as a sum of powers of two. In the same way, a cumulative frequency can be represented as a sum of sets of subfrequencies

  • 假设某一个index的二进制表示形式为01100，index为BIT数组中的下标i，那么index位置的值表示记录原数组哪些范围的值呢？
    • 最后一个1拆开的第一个数开始01001(9)~它自己(12)
    • 因此重点是找到最后一个1的位置，利用lowbit函数进行快速查找
  • 注：除原数组外，下标表示从1开始

lowbit函数

  • lowbit(i)：代表i这个数字，二进制表示的最后一位1的位权（最低为为1）

  • 例如（()内数字代表二进制，反之为10进制）

    1
    2
    3
    4
    5
    十进制			二进制	   只保留最低位1
    lowbit(8) => (1000) => (1000) => 8
    lowbit(6) => (0110) => (0010) => 2
    lowbit(12)=> (1100) => (0100) => 4
    lowbit(7) => (0111) => (0001) => 1

  • lowbit实现

    1. x & (-x)
    2. x & (~x + 1)

改进前缀和

  • C[i]： 代表原数组中a第i位 的前lowbit(i)项 之和

  • 例如

    1
    2
    3
    4
    # lowbit(10) = 2，所以是从10开始（含），一共两项
    lowbit(10) = 2, C[10] = a[10] + a[9]
    # lowbit(12) = 4，所以是从12开始（含），一共四项
    lowbit(12) = 4, C[12] = a[12] + a[11] + a[10] + a[9]

img

query：前缀和查询

  • S[i] = S[i – lowbit(i)] + C[i]

  • 例如

    1
    2
    3
    S[7] = s[7 - lowbit(7)] + c[7] = S[6] + C[7] = S[4] + C[6] + C[7] = C[4] + C[6] + C[7]

    S[12] = s[12 - lowbit(12)] + c[12] = S[8] + C[12] = C[8] + C[12]

update：单点更新

  • 假设修改a[j]，那么显然需要更新c[j]，然后需要修改包含c[j]的区间，即c[i + lowbit(i)]

一维BIT

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>

using namespace std;

#define lowbit(x) (x & (-x))

class FenwickTree {
private:
    int n; // 下标上限
    vector<int> c; // 树状数组

public :
    // 注意这里是n + 1
    FenwickTree(int size) : n(size), c(n + 1) {}

    // 对原数组进行单点增加 第i位的值增加x
    void add(int i, int x) {
        while (i <= n) c[i] += x, i += lowbit(i); // 向上更新
    }

    // 查询原数组 ind位置的值
    int at(int ind) { 
        return query(ind) - query(ind - 1); 
    }

    // 查询原数组 ind位置前缀和 
    int query(int ind) {
        int sum = 0;
        while (ind) sum += c[ind], ind -= lowbit(ind);
        return sum;
    }

    // 查询原数组 [left, right]区间和
    int queryRange(int left, int right) {
        return query(right) - query(left - 1);
    }

    // 以下非关键内容，仅为测试用
    // 测试输出
    void output() {
        int len = 0;
        for (int i = 1; i <= n; i++) {
            len += printf("%5d", i); // 打印坐标位
        }
        printf("\n");
        for (int i = 0; i < len + 6; i++) {
            printf("=");
        }
        printf("\n");
        for (int i = 1; i <= n; i++) {
            printf("%5d", c[i]); // 打印树状数组 
        }
        printf("\n");
        for (int i = 1; i <= n; i++) {
            printf("%5d", query(i) - query(i - 1)); // 打印原数组
        }
        printf("\n\n\n");
    }
};

int main() {
    int n;
    cin >> n;
    FenwickTree tree(n);
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        tree.add(i, a);
    }
    tree.output();
    int ind, val;
    while (cin >> ind >> val) {
        cout << "change " << ind << " to " << val << endl;
        // add函数是单点增加，所以需要求变化量
        tree.add(ind, val - tree.at(ind)); // 将原数组ind位置的值 改为val
        tree.output();
        cout << "range sum 1-3: " << tree.queryRange(1, 3) << endl;
        cout << "range sum 2-3: " << tree.queryRange(2, 3) << endl;
        cout << "range sum 2-4: " << tree.queryRange(2, 4) << endl;
    }
    return 0;
}

二维BIT

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>

using namespace std;

#define lowbit(x) (x & (-x))

class FenwickTree2 {
private:
    int n;  // 行下标上限
    int m;  // 列下标上限
    vector<vector<int>> c;  // 树状数组
    vector<vector<int>> a;  // 原始数组

public :
    // 注意这里是n + 1
    FenwickTree2(int n_, int m_) : n(n_), m(m_), c(n + 1, vector<int>(m + 1)), a(n, vector<int>(m)) {}

    // 对原数组进行单点增加 第i位的值增加x
    void add(int i, int j, int x) {
        a[i - 1][j - 1] += x;
        for (int row = i; row <= n; row += lowbit(row)) {
            for (int col = j; col <= m; col += lowbit(col)) {
                c[row][col] += x;
            }
        }
    }

    // 查询原数组 ind位置的值
    int at(int ind, int jnd) { 
        return query(ind, jnd) - query(ind - 1, jnd - 1); 
    }

    // 查询原数组 ind位置前缀和 
    int query(int ind, int jnd) {
        int sum = 0;
        for (int row = ind; row > 0; row -= lowbit(row)) {
            for (int col = jnd; col > 0; col -= lowbit(col)) {
                sum += c[row][col];
            }
        }
        return sum;
    }

    // 查询原数组 从[row1, col1]到[row2, col2]区间和
    int queryRange(int row1, int col1, int row2, int col2) {
        return query(row2, col2) - query(row1 - 1, col2) - query(row2 - 1, col1) + query(row1 - 1, col1 - 1);
    }

    // 以下非关键内容，仅为测试用
    // 测试输出
    void output() {
        int len = 0;
        for (int i = 1; i <= n; i++) {
            len += printf("%5d", i); // 打印坐标位
        }
        printf("\n");
        for (int i = 0; i < len + 6; i++) {
            printf("=");
        }
        printf("\n");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%5d", c[i][j]); // 打印树状数组 
            }
            printf("\n");
        }
        printf("\n");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%5d", a[i - 1][j - 1]); // 打印原数组
            }
            printf("\n");
        }
        printf("\n\n\n");
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    FenwickTree2 tree(n, m);
    for (int i = 1, a; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a;
            tree.add(i, j, a);
        }
    }
    tree.output();
    int ind, jnd, val;
    while (cin >> ind >> jnd >> val) {
        if (ind <= 0 || jnd <= 0) break;
        cout << "change " << ind << ", " << jnd << " to " << val << endl;
        // add函数是单点增加，所以需要求变化量
        tree.add(ind, jnd, val - tree.at(ind, jnd)); // 将原数组ind位置的值 改为val
        tree.output();
    }
    int row, col;
    while (cin >> row >> col) {
        if (row <= 0 || col <= 0) break;
        cout << "query [1, 1] => ["<< row << "," << col << "] " << tree.query(row, col) << endl;
    }
    return 0;
}

参考

  1. Binary Indexed Tree or Fenwick Tree
  2. Binary Indexed Tree or Fenwick Tree
  3. BINARY INDEXED TREES
  4. 前缀和/树状数组
  5. index Tree
  6. IndexTree
  7. IndexTree以及应用