树状数组是一种支持单点增加的维护前缀和（区间和）的数据结构。

一般求数组的中一段区间的和时，常用的方法有两种。一种是直接对数组对应的区间上进行遍历，来求出该区间元素的和。另一种方法是，申明一个相同长度的数组分别存放前i项和，通过 $O(n)$ 的时间复杂度得到前n项和数组，然后在每一次求数组区间和时就可以在 $O(1)$ 时间复杂度内得到结果。若数组会频繁更新，上述两种方法的求和效率就会变得很低了。

Binary Indexed Trees（简称BIT）又称为树状数组，主要用于解决对于一个频繁更新的数组求前 $n$ 项和（区间和）的问题。其查询和修改复杂度都为 $O(logn)$。树状数组可以在 $O(logn)$ 的时间复杂度内完成对数组值的更新，同时也可以在 $O(logn)$ 的时间复杂度内完成对数组的区间求和。

基本思想

树状数组的基本思想是，在树状数组中，每个元素保存原数组中一个或者多个连续的元素的和。在求数组区间的和时，只需要将树状数组中部分元素相加即可。

为了理清树状数组的工作原理，现在假设有一个长度为16的数组nums。在C++中表示如下：

1
int nums[16] = {3, 2, -1, 6, 5, 4 -3, 3, 7, 2, 3, -1, 4, 8, 1, 2};

为了解释方便，现在假设该数组以下标从1开始时的表示为A[1...n]。树状数组为C[1...n]。则树状数组中每个元素所保存的值与原数组的对应关系如下：

1
2
3
4
5
6
7
8
9
10
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

但从上面的等式中不容易发现规律，将其下标化为二进制表示如下

1
2
3
4
5
6
7
C001 = A001
C010 = A001 + A010
C011 = A011
C100 = A001 + A010 + A011 + A100
C101 = A101
C110 = A101 + A110
...

假设在树状数组中有一个节点 Cx 编号为 x ， x 二进制表示时末尾0的个数为k，则该节点表示的2^k个原数组中连续元素，并且以Ax结尾，即Cn = A(n – 2^k + 1) + ... + An。

借用百度百科)上的图片，当原数组的元素个数为16时，可视化的表示如下。

img

按照树状数组中的结构，若要计算数组A的前15项的和，则只需要计算出C[15]+C[14]+C[12]+C[8]。计算数组A的前16项和，则只需要计算出C[16]。

此时，来看看下标15、14、12、8之间有什么规律。这四个数的二进制表示为1111、1110、1100、1000。再结合上文中所描述，树状数组中每个元素中所表示的特点可知，若要求前n项和的方法如下。其中idx -= (idx & -idx);为idx去掉其二进制表示时最右侧的1来得到下一个idx的值。

1
2
3
4
5
6
7
8
9
10
// 计算数组nums_下标为0到下标为i的所有元素的和。
int getSum(int i) {
    int sum = 0;
    int idx = i+1;
    while (idx > 0){
        sum += tree_[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

与获得前n项和的原理相同，若原数组中有需要更新时，则需要将树状数组中包含该节点值的元素都做更新。根据树状数组数据结构的特点，从下标idx开始，依次使其二进制表示时最右侧为1的位置加1即可得到所有需要在树状数组中更新的元素的下标。

1
2
3
4
5
6
7
8
9
10
// 将数组nums_下标为i的元素更新为val，同时更新树状数组
void update(int i, int val) {
    int idx = i+1;
    int tem = val-nums_[i];
    nums_[i] = val;
    while (idx <= maxidx_) {
        tree_[idx] += tem;
        idx += (idx & -idx);
    }
}

除了用于求可变数组的区间和之外，树状数组还可用于求原数组中在一定区间内出现的频率问题（累计频率问题），如数组中某元素右侧大于该元素的元素个数有多少个。例leetcode-307、leetcode-493等。

实现代码

实现代码中，数组num_保存了原数组的值，树状数组为tree_，其中tree_[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
inline int lowbit(int x) {
    return x&(-x);
}
class NumArray {
 public:
    NumArray(vector<int>& nums) {
        maxidx_ = nums.size();
        nums_ = vector<int>(maxidx_, 0);
        tree_ = vector<int>(maxidx_ + 1, 0);
        for (int i = 0; i < nums.size(); ++i)
            update(i, nums[i]);
    }

    // 将数组nums_下标为i的元素更新为val，同时更新树状数组
    void update(int i, int val) {
        int idx = i+1;
        int tem = val-nums_[i];
        nums_[i] = val;
        while (idx <= maxidx_) {
            tree_[idx] += tem;
            idx += (idx & -idx);
        }
    }

    // 计算数组nums_从下标i到下标j的所有元素的和，闭区间
    int sumRange(int i, int j) {
        return getSum(j) - getSum(i-1);
    }
    
    // 计算数组nums_从下标为0到下标为i的所有元素的和。
    int getSum(int i) {
        int sum = 0;
        int idx = i+1;
        while (idx > 0){
            sum += tree_[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

 private:
    int maxidx_;
    vector <int> tree_;
    vector <int> nums_;
};

树状数组与逆序对

待补充

区间增加的树状数组

在原数组上构建差分数组，再再查分数组上建立树状数组可以用于区间增加的操作。

待补充

参考文献

https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html

https://www.youtube.com/watch?v=2SVLYsq5W8M

https://blog.csdn.net/L664675249/article/details/50157669

https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/

https://baike.baidu.com/item/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84