树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。
事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以．然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值．
我们学习数据结构的目的在于将我们的算法变得更快。由 Peter M. Fenwick 提出的树状数组 BIT 结构（Fenwick 树）就是一个优秀的数据结构，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;
}这种方式第一个操作，也就是计算累加和的时间复杂度为\( O(n) \) ，更新操作的时间复杂度为\( O(1) \) ;
另外一种方式就是创建一个大小为 n 的新数组，并且在新数组的第 **i** 个位置保存前 **i** 个元素的累加和。此时查找给定范围内的累加和就可以在\( O(1) \) 的时间内完成，但是更新操作将花费\( O(n) \) 的时间，。
// 更新数组 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];
}
}也就说，要实现上面提到的两个操作，要么查找为\( O(n) \) ，更新操作为\( O(1) \) ；要么使用额外的空间，将查找操作降为\( O(1) \) ，但是更新操作变为了\( O(n) \) .
树状数组
那么是否可以将查找和更新操作同时降低到\( O(logn) \) 呢？
一个就是以后会讲到的，另外一个就是树状数组 （Binary Indexed Tree），两者均可以将上面所提到的查找和更新操作的时间复杂度降到 。但是，并且易于实现。
树状数组表示为 BITree[]；树状数组的每个节点存储输入数组中某些元素的和；树状数组的大小等于输入数组的大小，记作 n 。为了便于实现，BITree[] 使用 n+1 的大小。
首先，我们给出一个数组 arr[] :
然后直接直观地看一下针对这个数组 arr[] 的树状数组：
事实上这棵树并不存在，树状数组依然只是下面的一个数组而已：
现在的问题是**<font style="color:#D22D8D;">arr[]</font>****<font style="color:#D22D8D;">BITree[]</font>**？
答案很简单：
- 首先将树状数组
BITree[]的所有元素初始化为 0； - 调用
updateBITree()函数更新BITree[]数组即可。
所以关键就是实现 updateBITree() 函数啦！
实现（敲代码）不是关键，重要的是理解为什么！
我们先来细致地看一趟 updateBITree() 函数的执行过程：
第一步：index = 1 ，将 BITree[1] = BITree[1] + arr[0] :
第二步：更新 **index = index + index & (-index) = 1 + 1 = 2** ，这里你可能一头雾水，没关系，这篇文章最后没有让你彻底明白树状数组，你大可喷我！我暂且不解释它的含义和作用，我们仅仅解释一下 **index & (-index)** 表示什么。**<font style="color:#DF2A3F;">index & (-index)</font>****<font style="color:#DF2A3F;">index</font>**，例如 6 & (-6) ，6 的二进制为 110 ，从右向左数，第一个 1 的位置是 2 ，那么 **6 & (-6) = 2** 。当然这是二进制运算之中取最后一个 1 的小诀窍，下面是的，以一个32位的机器为例：
这里如果有问题，大家可以看一下 剑指 offer 面试题精选图解 15 . 二进制中1的个数 这篇文章，然后复习一下原码、反码和补码接着看。
**具体含义: **
index & (-index)得到的是index的 lowbit，即二进制表示中最低位的1所代表的值（例如 6 的二进制110，lowbit = 2）。- 加上这个 lowbit 后，结果相当于将最低位的 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() 函数的执行结束啦！知道你没啥感觉更是没有体会到树状数组的妙用（我刚开始也是，说实话，笨笨的大禹看了好几天）。
但是当你将所有的步骤都都走完之后，你就会感觉不一样啦！
对角线的值就是一开头的图里的 BITree[i]，可以发现 \( Index = 2^k \)\( 2^k \)：
图中没有填充的单元格都表示 0，第 1 趟 updateBITree() 函数确定了 **BITree[1]** 的值，<font style="color:#D22D8D;">updateBITree()</font>**<font style="color:#D22D8D;">BITree[2]</font>**，以此类推，第 12 趟 updateBITree() 函数确定了 **BITree[12]** 的值，也就是结果 12 （12就是数组 arr[] 的大小）趟更新，我们得到了我们的主角 **BITree[]** 树状数组：
也就是，我们完成了从数组 **arr[]** 到 **BITree[]** 的过渡。
下面我要告诉你的才是树状数组的关键和核心奥！
**<font style="color:#DF2A3F;">BITree[]</font>**。
假设现在的原始数组 arr[] 的大小 n = 16 ，我们看下标 1 到 16 到底如何成为树状数组的关键所在的。
对于上面的每一个 index , 均计算 **index & (-index)** 的值，比如 10，可以计算得到 **10 & (-10) = 2** ，实在不会也没关系，就把 10 转化为二进制 1010 ，然后从右向左数数，碰到的第一个 1 的位置就是 2 （其他数字的计算都是一样的过程，就不过多说明）。
而这个 **index & (-index)** 所对应的值有何意义呢？
答案，**index & (-index)** 表示一个范围，千篇一律的叫法叫做 **<font style="color:#DF2A3F;">Lowbit(index)</font>**。
以 **index & (-index)** 中的第一个 1 为例，**<font style="color:#D22D8D;">arr[]</font>**<font style="color:#D22D8D;">BITree[index]</font>，即 **BITree[1] = 2** .
那么 **BITree[]** 数组中的值 30 的由来就更好解释了，，即 9 + 8 + 7 + 6 = 30
对于 **index & (-index)** 中的其他元素的解释是同样的道理。但是 **index & (-index)** 所表示的数组你以为就这样简单吗？若真是如此，估计我就不讲了。
就一棵树而言，必定有父子之分，那么树状数组是如何体现父子关系的呢？
**<font style="color:#DF2A3F;">BITree[y]</font>****<font style="color:#DF2A3F;">BITree[x]</font>******当且仅当 y 可以通过从 x 的二进制表示中删除最后一个位置的 1 （也就是从右向左第一个） 来获得，即<font style="color:#DF2A3F;">y = x - (x & (-x)) = x - lowbit(x)</font>BITree[y]的BITree[x]存储的是数组arr[]中**<font style="color:#DF2A3F;">arr[y,...,x)</font>**
有了这样的父子关系，仅使用 **index & (-index)** 就可以直观地构建出我们期待已久的树状数组中所谓的树。
已知 **index** 和 **index & (-index)** ，计算两者之差简直轻而易举：
那么构建一颗树还难吗？一点儿都不。
同理，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 （也就是从右向左第一个） 来获得，****<font style="color:#DF2A3F;">y = x - (x & (-x))</font>**BITree[y]的BITree[x]存储的是数组arr[]中**<font style="color:#ED740C;">arr[y,...,x)</font>**
关于这个第三条可能需要稍微解释一下：
**BITree[8]** 的孩子结点 **BITree[12]** 的值等于 30 ，表示数组 arr[] 中下标从 8 到 12（不包含 12）的元素的累加和，即 **BITree[12] = 30 = arr[8,...,12) = 6 + 7 + 8 + 9** 。
其实这里就和之前我们介绍的 **index & (-index)** 所表示含义不谋而合。
是不是有点儿清晰呢？很快你就会看到一句话概括上面所讲的所有内容。
回到我们最开始的两个问题。
如何根据 BITree[] 树状数组，获取数组 arr[] 中前 i 个元素的累加和？
这里更关键奥！！！
我们都知道，，比如 11 可以表示为 8 + 2 + 1.** **BITree**的每个节点都存储 n 个元素的总和，其中 n 是 2 的次幂**。比如前 11 个元素的累加和可以通过对原数组 arr[] 中最后 1 个元素（第11个元素）、向前两个元素（第 9 和 10 号元素）和 前 8 个元素 （从 1 到 8 的）的元素之和求得。
对照上图，来理解文字描述就更清晰了，三者的和。
如果从树状数组的角度来看，**BITree[8] = 21** 表示前 8 个元素的累加和，**BITree[10] = 13** 表示 6 和 7 的和（这里解释一下， \( 10 \&(-10) = 2 \) 表示的就是两个数的和）， **BITree[11] = 8** 表示一个 8 （\( 11 \&(-11) = 2 \)，表示 1 个数的和） 。所以前 11 个元素的累加和等于 **BITree[8] + BITree[10] + BITree[11] = 21 + 13 + 8 = 42** 。
如果再从更直观的树上看，，然后将路径上的值都加起来，就是前 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[]** ，时间复杂度为\( O(logn) \) :
index = 4 ，将 BITree[index] += val ，即 BITree[4] = 7 + 6 = 13 .
更新 index ，index = index <font style="color:#DF2A3F;">+</font> 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);
}
}能否将树状数组扩展到以\( O(logn) \)的时间复杂度计算呢？
答案是肯定的，rangSum(l,r) = getSum(r) - getSum(l - 1) .
复杂度分析
任何一个正整数 n 的二进制表示中置位数的个数为\( O(nlogn) \) 量级，。因此，getSum() 和 updateBIT() 两个操作至多遍历\( O(logn) \) 个结点。
初始构造树状数组 BITree[] 的时间复杂度为\( O(nlogn) \)，构造 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));
}
}