这篇文章介绍了一种叫做树状数组（Binary Indexed Tree）的数据结构，与之前提到的线段树一样，这种数据结构可以解决“求区间内元素之和”的Random Query问题，并且其初始化的时间复杂度是O(n)、更新和查询的时间复杂度都是O(logn)。

一、概览

就和线段树本质上是一棵二叉树一样，树状数组本质上就是个数组。假设输入的数组是a[1...n]，我们可以在该数组的基础上建立树状数组e[1...n]，该数组的长度与原数组相同，而该数组中的每个元素则对应原数组中一个或者多个元素的和。什么叫对应原数组中一个或者多个元素的和呢？我们可以观察下面的一组等式，找一找规律：

e[1] = a[1]
e[2] = a[1] + a[2]
e[3] = a[3]
e[4] = a[1] + a[2] + a[3] + a[4]
e[5] = a[5]
e[6] = a[5] + a[6]
e[7] = a[7]
e[8] = a[1] + a[2] + a[3] + a[4] + … + a[8]

或者参照下面的图片。该图片也展示了树状数组e和原数组a中元素的对应关系：

二、查询

那么树状数组e和原数组a到底有什么对应关系呢？我们可以设想：对于一个正整数num，我们可以求得一个最大的非负整数，它满足：该整数小于num，且二进制表示中末尾的0个数比num多。举几个例子：如果num=5，我们所求得的整数就应该是4；如果num=6，我们所求得的整数仍然是4；如果num=8，我们所求得的整数就应该是0。
我们把我们所求得的整数记作prev(num)，然后我们就得到了树状数组e和原数组a的对应关系：e[num] = a[prev(num)+1] + ... + a[num]。

prev(num)的求法

我们定义一个函数lowbit(num)，该函数的结果保留了num最低位的1，而将它左边的所有位全部清零。比如对于num=5，lowbit(num) = 1；对于num=6，lowbit(num) = 2；对于num=8，lowbit(num) = 8。该函数的实现如下：

1
2
3

int lowbit(int num){
    return (num ^ (num-1)) & num;
}

观察上面代码我们知道，(num-1)是将num最低位的1变成0，然后将这一位右边的0全部变成1，这一位左边的部分不变。num^(num-1)则将这一位左边的部分全部清零，并将这一位和这一位右边的所有位全部变为1。最后，将num^(num-1)与num按位与，这一位左边的所有位在num^(num-1)中是0，所以在最终结果中是0；这一位右边的所有位在num中是0，所以在最终结果中是0；只有这一位本身在num^(num-1)和num中都是1，所以在结果中也是1。这样就达到了只保留num最低位的1的效果。
有了lowbit(num)，计算prev(num)也就水到渠成：

1
2
3

int prev(int num){
    return num - lowbit(num);
}

查询的方法

给定一个下标i，我们如何求sum(i) = a[1]+...+a[i]？
通过访问数组e，我们可以得到e[i] = a[prev(i)+1]+...+a[i]，在这个基础上，只要求出sum(prev(i))，将这个值加上e[i]，就得到了我们要求的sum(i)。不难看出，这是一个重复的子过程，我们可以利用递归或者迭代轻易地实现：

1
2
3
4
5
6
7
8
9
10

int sum(int i){ //输出a[1]+...+a[i]的值。
    int res = 0;
    int index = i;
    while(index > 0){
        res += sumArr[index];
        int lowBit = (index ^ (index-1)) & index;
        index -= lowBit;
    }
    return res;
}

在定义了sum函数之后，对于每次查询，输入下标i和j，要输出这之间元素之和，代码就比较简单了：

1
2
3
4
5
6

int sumRange(int i, int j) {
    if(i == 1)
        return sum(j);
    else
        return sum(j) - sum(i-1);
}

对照着上面的图片我们可以看出，在求sum(i)的过程中，最坏情况下我们要迭代log(i)次。所以对于每次查询，其时间复杂度可以认为是O(logn)。

三、初始化

与刚才定义prev(num)同样，我们可以定义next(num)，该函数输出比num大的、第一个二进制末尾的0比num多的整数。

1
2
3

int next(int num){
    return num + lowbit(num);
}

树状数组初始化的流程可以简要叙述为：
1. 对于所有的i，令 e[i] = a[i]。
2. 令i从1到n递增，对于每个i，如果next(i)没有越界，令e[next(i)] += e[i]。
这就完成了树状数组的初始化，可以观察数组长度为6的情况：

对应的代码如下：

1
2
3
4
5
6
7
8
9

//初始化sumArr：
for(int i=1; i<=size; i++)
    sumArr[i] = nums[i];
for(int i=1; i<=size; i++){
    int lowBit = (i ^ (i-1)) & i;
    int nextIndex = i + lowBit;
    if(nextIndex <= size)
        sumArr[nextIndex] += sumArr[i];
}

可以发现，树状数组的初始化相当于两次遍历，所以时间复杂度为O(n)。

四、更新

假设我们要修改下标为i的元素a[i]的值，我们只需要更改数组e中的一部分值，这一点和线段树是相同的。
对照上面的图片，找到下标为i的列然后从下往上看，我们很容易发现需要修改的元素都是哪些。比如在上面的图中，对于i=9而言，要修改的元素分别是e[9]、e[10]、e[12]和e[16]。我们可以发现，它们正好对应着9、next(9)、next(next(9))……
由此我们可以总结出更新树状数组的代码：

1
2
3
4
5
6
7
8
9
10

void update(int i, int val) { //val是新的值
    int index = i;
    int delta = val - nums[i]; //计算一个相对于原值的变化量
    nums[i] = val;
    while(index <= size){
        sumArr[index] += delta;
        int lowBit = (index ^ (index-1)) & index;
        index += lowBit;
    }
}

与查询一样，在最坏情况下我们要迭代log(i)次。所以对于每次更新，其时间复杂度也可以认为是O(logn)。

五、总结

树状数组本质上是按照二分对数组进行分组，其初始化的时间复杂度为O(n)，更新和查询的时间复杂度都是O(logn)。与线段树相比，树状数组能够解决的问题类型有限，它不能解决线段树能够解决的查询最大/最小值类问题。但是相对于线段树而言的好处是，它的实现较为简单，并且虽然用大O表示时二者的时间复杂度相同，但是树状数组前面乘以的常数项较小，所以总体上其效率还是要高于线段树的。