问题的提出

有一个数组 nums[0 . . . N-1]，我们希望能提供如下两个功能：

功能1：求出前 i 个元素的和 sum功能2：改变某个元素的值，即nums[i] = x

请参考 LeetCode 307. Range Sum Query - Mutable

一般情况下，功能1的时间复杂度为O(N)，功能2的时间复杂度为O(1)。 如果要改进功能1时间复杂度，我们可以依赖一个前缀和数组sum，用于记录前 i 个元素的和，即 sum[i] = nums[0] + nums[1] + ... + nums[i]。但此时，功能2的时间复杂度变为了O(N)，因为需要去维护数组 sum。

树状数组就是用来平衡这两个时间复杂度的，可以使得功能1和功能2的时间复杂度都为O(logN)。

引子 —— 一个位运算

获取数字 X 的最低比特位的计算式f(X)= X & -X 这个位运算举几个例子就大致明白了，具体证明也很简单，因为负数补码是正数按位取反再加1。实在不明白记住就行了，在此不再偏题赘述。

树状数组方法

创建数组BITree（图片中对应为数组C）

对于数组 a，我们设一个数组 BITree，有 BITree[i]=a[i-f(i)+1]+a[i-f(i)+2]+...+a[i]。 其中f(i)就是取最低比特位的函数。 这里的数组a和BITree都是从1开始算的，把索引0位置置零即可！ 下图的C即为数组BITree，lowbit(i)即为f(i)

计算i到j的和

计算方法：

sum(i,j)=sum(j)-sum(i-1)

代码如下：

public int sumRange(int i, int j) { i++; j++; return sum(j) - sum(i - 1); }

上述的i++和j++是索引0到索引1的转化过程。

接下来就要提供一个计算前缀和sum(index)的方法。 具体算法是

public int sum(int index) { int res = 0; while (index > 0) { res += BITree[index]; index = index - (index & -index); } return res; }

即 $$sum(k)=BITree[n_1]+\cdots +BITree[n_m]$$ 其中 $$n_m=k,n_{i-1}=n_i-f(n_i),n_1=f(n_1)$$ 例如 $$sum(6)=BITree[6]+BITree[4]$$

sum的构成证明

按照BITree的定义，展开每一项即可

求和复杂度证明

为了证明sum(i,j)复杂度是O(logN)，只需要证明sum(N)复杂度为O(logN)，证明思路为每次N都去掉了最低的二进制位，故最多循环O(logN)次。

更新算法

先更新a[i]，再调用updateBIT方法更新BITree数组

public void update(int i, int val) { i++; int diff = val - a[i]; a[i]=val; updateBIT(i, diff); }

这里又涉及到判断BITree中哪些项需要更新。 具体代码如下：

private void updateBIT(int i, int diff){ while (i < arr.length) { BITree[i] += diff; i = i + (i & (-i)); } }

更新规则如下：

更新过程的证明

采用数学归纳法

一个例子

LeetCode 307. Range Sum Query - Mutable 的代码解答

class NumArray { private int[] a; private int[] BITree; public NumArray(int[] nums) { a = new int[nums.length + 1]; System.arraycopy(nums, 0, a, 1, nums.length); BITree = new int[nums.length + 1]; // 初始化BITree数组 int[] sum = new int[nums.length + 1]; for (int i = 1; i < sum.length; i++) { updateBIT(i, a[i]); } } public void update(int i, int val) { i++; int diff = val - a[i]; a[i]=val; updateBIT(i, diff); } private void updateBIT(int i, int diff){ while (i < a.length) { BITree[i] += diff; i = i + (i & (-i)); } } public int sumRange(int i, int j) { i++; j++; return sum(j) - sum(i - 1); } private int sum(int index) { int res = 0; while (index > 0) { res += BITree[index]; index = index - (index & -index); } return res; }

参考链接

【1】https://www.jianshu.com/p/455fd78637be 【2】北大 acm 暑期课