我们学习数据结构的目的在于将我们的算法变得更快。由 Peter M. Fenwick 提出的树状数组 BIT 结构就是一个优秀的数据结构，BIT 全称 Binary Indexed Trees 结构，而不是所说的比特奥。Peter M. Fenwick 首次使用此结构进行数据压缩。在算法竞赛中，通常用于存储频率和处理累积频率表。
首先考虑一个简单的问题。
给定一个数组 arr[0 ... n-1] ，如何实现下面两个操作：
- 计算前 i 个元素的累加和；
- 将数组中下标为 i 的元素的值更新为 x，
arr[i] = x ，其中 0 <= i <= n-1
一个简单的方法就是遍历 0 到 i - 1 的元素并计算出累加和即可 ；然后更新操作 arr[i] = x 就可以直接进行，也就说可以对数组 arr[] 直接进行修改.
// 计算前 i 个元素的累加和
public int getSum(int arr[], int i){
int sum = 0;
for(int j = 0; j < i; j++){
sum += arr[j];
}
return sum;
}
这种方式第一个操作，也就是计算累加和的时间复杂度为 ，更新操作的时间复杂度为
另外一种方式就是创建一个大小为 n 的新数组，并且在新数组的第 i 个位置保存前 i 个元素的累加和。此时查找给定范围内的累加和就可以在 的时间内完成，但是更新操作将花费
// 更新数组 arr[i] = x 之后
// 需要对存储累加和的数组 new_arr 进行的修改。
void updateSum(int arr[], int i, int x){
arr[i] = x;
for(int j = i; j < new_arr.length; j++){
new_arr[j] = new_arr[j-1] + arr[j];
}
}
也就说，要实现上面提到的两个操作，要么查找为 ，更新操作为 ；要么使用额外的空间，将查找操作降为 ，但是更新操作变为了
树状数组
那么是否可以将查找和更新操作同时降低到
一个就是以后会讲到的线段树（Segment Tree），另外一个就是树状数组 （Binary Indexed Tree），两者均可以将上面所提到的查找和更新操作的时间复杂度降到
树状数组表示为 BITree[]；树状数组的每个节点存储输入数组中某些元素的和；树状数组的大小等于输入数组的大小，记作 n 。为了便于实现，BITree[] 使用 n+1 的大小。
首先，我们给出一个数组 arr[] :
然后直接直观地看一下针对这个数组 arr[] 的树状数组：
事实上这棵树并不存在，树状数组依然只是下面的一个数组而已：
现在的问题是如何从原始数组 arr[] 得出树状数组 BITree[]
答案很简单：
- 首先将树状数组
BITree[] 的所有元素初始化为 0； - 调用
updateBITree() 函数更新 BITree[] 数组即可。
所以关键就是实现 updateBITree() 函数啦！
实现（敲代码）不是关键，重要的是理解为什么！
我们先来细致地看一趟 updateBITree() 函数的执行过程：
第一步：index = 1 ，将 BITree[1] = BITree[1] + arr[0] :
第二步：更新 index = index + index & (-index) = 1 + 1 = 2 ，这里你可能一头雾水，没关系，这篇文章最后没有让你彻底明白树状数组，你大可喷我！我暂且不解释它的含义和作用，我们仅仅解释一下 index & (-index) 表示什么。index & (-index) 表示将 index 所代表的值转化为二进制之后，从右向左数，第一个 1 的位置，例如 6 & (-6) ，6 的二进制为 110 ，从右向左数，第一个 1 的位置是 2 ，那么 6 & (-6) = 2 。当然这是二进制运算之中取最后一个 1 的小诀窍，下面是的，以一个32位的机器为例：
这里如果有问题，大家可以看一下 剑指 offer 面试题精选图解 15 . 二进制中1的个数 这篇文章，然后复习一下原码、反码和补码接着看。
第三步：index = 2 ，将 BITree[2] = BITree[2] + arr[0] :
第四步：更新 index = index + index & (-index) = 2 + 2 = 4
第五步：index = 4 ，将 BITree[4] = BITree[4] + arr[0] :
第六步：更新 index = index + index & (-index) = 4 + 4 = 8
第七步：index = 8 ，将 BITree[8] = BITree[8] + arr[0] :
第八步：更新 index = index + index & (-index) = 8 + 8 = 16 ，16 > 12 ，已经超出了树状数组 BITree[] 的下标，一趟 updateBITree() 函数的执行结束啦！知道你没啥感觉更是没有体会到树状数组的妙用（我刚开始也是，说实话，笨笨的大禹看了好几天）。
但是当你将所有的步骤都都走完之后，你就会感觉不一样啦！
图中没有填充的单元格都表示 0，第 1 趟 updateBITree() 函数确定了 BITree[1] 的值，第 2 趟 updateBITree() 函数确定了 BITree[2] 的值，以此类推，第 12 趟 updateBITree() 函数确定了 BITree[12] 的值，也就是结果 12 （12就是数组 arr[] 的大小）趟更新，我们得到了我们的主角 BITree[]
也就是，我们完成了从数组 arr[] 到 BITree[] 的过渡。
下面我要告诉你的才是树状数组的关键和核心奥！
树状数组的关键不是 BITree[] ，而是 下标 。
假设现在的原始数组 arr[] 的大小 n = 16 ，我们看下标 1 到 16 到底如何成为树状数组的关键所在的。
对于上面的每一个 index , 均计算 index & (-index) 的值，比如 10，可以计算得到 10 & (-10) = 2 ，实在不会也没关系，就把 10 转化为二进制 1010 ，然后从右向左数数，碰到的第一个 1 的位置就是 2 （其他数字的计算都是一样的过程，就不过多说明）。
而这个 index & (-index)
答案，index & (-index) 表示一个范围，千篇一律的叫法叫做 Lowbit(index)。
以 index & (-index) 中的第一个 1 为例，它表示将数组 arr[] 中当前位置向前累加 1 个数字，作为 BITree[index] 的值，即 BITree[1] = 2
那么 BITree[] 数组中的值 30 的由来就更好解释了，就是从当前元素 9 向前累加 4 个元素（包含自身），即 9 + 8 + 7 + 6 = 30
对于 index & (-index) 中的其他元素的解释是同样的道理。但是 index & (-index)
就一棵树而言，必定有父子之分，那么树状数组是如何体现父子关系的呢？
-
BITree[y] 是 BITree[x] 的父结点，当且仅当 y 可以通过从 x 的二进制表示中删除最后一个位置的 1 （也就是从右向左第一个） 来获得，即 y = x - (x & (-x))
有了这样的父子关系，仅使用 index & (-index)
已知 index 和 index & (-index)
那么构建一颗树还难吗？一点儿都不。
比如 y 等于 0 ，视线向上找到对应的 index，分别为 1、2，4、8、16，也就是说，0是 1、2、4、8、16 的父结点；
同理，2 是 3 的父结点、4 是 5 和 6 的父结点、6 是 7 的父结点、8 是 9 和 10 的父结点，10 是 11 和12 的父结点、12 是 13 和 14 的父结点，14 是 15 的父结点。
就得到了下图：
这棵树的得出与原数组 arr[] 本身没有关系，而仅仅与下标 index 有关。而我们最开始所看到的树同样如此（只不过树中结点的真正的值是我们所计算出的 BITree[index]
树状数组的几大特点：
- BITree[0] 是一个虚拟结点，同时也是我们所看到的根结点
-
BITree[y] 是 BITree[x] 的父结点，当且仅当 y 可以通过从 x 的二进制表示中删除最后一个位置的 1 （也就是从右向左第一个） 来获得，即 y = x - (x & (-x)) -
BITree[y] 的孩子结点 BITree[x] 存储的是数组 arr[] 中下标从 y (包含) 到 x (不包含) 的累加和，即 arr[y,...,x)
关于这个第三条可能需要稍微解释一下：
BITree[8] 的孩子结点 BITree[12] 的值等于 30 ，表示数组 arr[] 中下标从 8 到 12（不包含 12）的元素的累加和，即 BITree[12] = 30 = arr[8,...,12) = 6 + 7 + 8 + 9
其实这里就和之前我们介绍的 index & (-index)
是不是有点儿清晰呢？很快你就会看到一句话概括上面所讲的所有内容。
回到我们最开始的两个问题。
如何根据 BITree[] 树状数组，获取数组 arr[] 中前 i 个元素的累加和？
这里更关键奥！！！
我们都知道，任何一个正整数都可以被表示为 2 的次幂和，比如 11 可以表示为 8 + 2 + 1. BITree的每个节点都存储 n 个元素的总和，其中 n 是 2 的次幂。比如前 11 个元素的累加和可以通过对原数组 arr[] 中最后 1 个元素（第11个元素）、向前两个元素（第 9 和 10 号元素）和 前 8 个元素 （从 1 到 8 的）的元素之和求得。
对照上图，来理解文字描述就更清晰了，我们求前 11 个元素的累加和，可以将其分解为 2 的次幂之和，即 8 + 2 + 1，也就是前 8 个元素的累加和（1 到 8），紧挨着的 2 个元素（9 和 10），和最后 1个元素 （11）三者的和。
如果从树状数组的角度来看，BITree[8] = 21 表示前 8 个元素的累加和，BITree[10] = 13 表示 6 和 7 的和（这里解释一下， 表示的就是两个数的和）， BITree[11] = 8 表示一个 8 （ ，表示 1 个数的和） 。所以前 11 个元素的累加和等于 BITree[8] + BITree[10] + BITree[11] = 21 + 13 + 8 = 42
如果再从更直观的树上看，计算前 11 个元素的累加和，从叶子结点 11 开始，找到 11 的父结点 10，然后找到 10 的父结点 8 ，8 的父结点为 0 ，然后将路径上的值都加起来，就是前 11 个元素的累加和。
不难写出下面计算累加和的代码：
int getSum(int index)
{
int sum = 0; // 累加和
// BITree[] 的下标比 arr[] 大 1
index = index + 1;
// 遍历 BITree[index] 的祖先结点
while(index>0)
{
// 将当前 BITree 的值加到 sum
sum += BITree[index];
// 将 index 指向 index 的父结点
index = index - index & (-index);
}
return sum;
}
代码很清晰，就是从给定的 index 遍历 index 的所有的祖先结点，并将遍历到的 BITree[index] 的值加起来即可。
如何将数组中下标为 i 的元素的值更新为 x，且在 O(logn) 的时间内更新树状数组 BITree[]
虽然关于这个问题在最开始的时候已有阐述，但我们再以一个例子介绍一遍！
现在将 arr[3] = arr[3] + 6 ，时间复杂度为
然后更新树状数组 BITree[] ，时间复杂度为
index = 4 ，将 BITree[index] += val ，即 BITree[4] = 7 + 6 = 13 .
更新 index ，index = index + index & (-index) = 4 + 4 = 8 ;
更新 BITree[index] ，即 BITree[8] = 21 + 6 = 27 :
更新 index ，index = index + index & (-index) = 8 + 8 = 16 > 12 ，更新过程结束。
代码也相当简单：
public static void updateBIT(int n, int index, int val)
{
// BITree[] 的下标比 arr[] 大 1
index = index + 1;
// 遍历所有的祖先，并加上 'val'
while(index <= n)
{
// BIT Tree 的当前结点加上 'val'
BITree[index] += val;
// 更新 index
index += index & (-index);
}
}
能否将树状数组扩展到以
答案是肯定的，rangSum(l,r) = getSum(r) - getSum(l - 1) .
复杂度分析
任何一个正整数 n 的二进制表示中置位数的个数为 量级，置位数就是一个整数二进制表示中 1 的数目。因此，getSum() 和 updateBIT() 两个操作至多遍历
初始构造树状数组 BITree[] 的时间复杂度为 ，构造 BITree[] 树状数组会调用 updateBIT() 函数 n 次。
完整的实现代码
import java.util.*;
import java.lang.*;
import java.io.*;
class BinaryIndexedTree
{
final static int MAX = 100;
static int BITree[] = new int[MAX];
int getSum(int index)
{
int sum = 0;
index = index + 1;
while(index>0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
public static void updateBIT(int n, int index,
int val)
{
index = index + 1;
while(index <= n)
{
BITree[index] += val;
index += index & (-index);
}
}
void printBITree(int arr[], int n) {
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
void constructBITree(int arr[], int n)
{
for(int i=1; i<=n; i++)
BITree[i] = 0;
for(int i = 0; i < n; i++) {
updateBIT(n, i, arr[i]);
printBITree(BITree,n+1);
}
}
public static void main(String args[])
{
int arr[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
int n = arr.length;
BinaryIndexedTree tree = new BinaryIndexedTree();
// 从给定的数组 arr[], 构造 BITree[]
tree.constructBITree(arr, n);
System.out.println("arr[0..5] = " + tree.getSum(5));
// 测试更新操作
arr[3] += 6;
// arr[3] 的改变，更新 BITree[]
updateBIT(n, 3, 6);
System.out.println("arr[0..5] = " + tree.getSum(5));
}
}
---