以前刚开始学习树状数组的时候很迷，不知道为啥会出现一个这么抽象的玩意儿，也仅仅是将树状数组怎么使用给背下来了。

在刚开始学了树状数组之后并没有怎么使用，差不多能用树状数组解决的问题都用线段树解决了。

后来看了《挑战程序设计》里面关于树状数组的推导之后才对于树状数组有了一个稍微深刻一些的认识，还是要感叹既然有这种数据结构的出现那么就必然有它存在的道理，人类的智慧是无穷的。

 

要学习树状数组首先要明白树状数组是用来干啥的。它一般用于这么两个操作

• 求数列的前缀和
• 在数列的某一个数上面加上一个数

如果没有学习过树状数组，或者对于树状数组不熟悉使用线段树也可以很轻松的解决。但是写过线段树的同学都知道，线段树写起来是有一点复杂的，需要写建树，插入，更新，询问等操作。但是树状数组在实现方法上方便了很多，同时在解决这连个问题上，树状数组可以更快地解决。

那么先说线段树，如果在线段树中求前缀和你会发现你最终的答案如果是从树中找到的几个节点的和，那么这几个节点一定是线段树中的左儿子。如图所示，如果你要找1~7的区间和，那么肯定会产生图上所示的结果。

　　　　　　　　　　　　　　　　　　　

那既然求前缀和在线段树中并不会用到右儿子，可不可以将右儿子全删掉呢？那么删掉试试看

　　　　　　　　　　　　　　　　　　

这不就是树状数组了吗，但是有的人有疑问，如果将右儿子删掉了那么在从根节点往下找的时候怎么找呢。无法从上往下找可以从叶子节点往上找啊。所以看树状数组的实现方法，可以很简单的使用一些二进制位上的操作来从叶子节点往上查找。

int bit[MAX_N + 1],n;int sum(int i) {    int s = 0;    while(i) {        s += bit[i];        i -= i&-i;    }    return s;}void add(int i,int x) {    while(i <= n) {        bit[i] += x;        i += i*&-i;    }}

 

 

其实树状数组适用的范围要比线段树小很多，个人感觉两者在时间复杂度上面相差不是很多，树状数组的主要优势就是写法很简便，没有线段树那么复杂，这样就可以避免手贱写BUG。