【算法】[转] 搞懂树状数组

原文链接

写下这个标题，其实心里还是没底的，与其说是写博帖，不如说是做总结。第一个接触树状数组还是两年前，用什么语言来形容当时的感觉呢？……太神奇了！真的，无法表达出那种感觉，她是那么的优雅，10 行不到的代码，却把事情干的如此出色！没有了解她原理的前提下即使把代码倒背如流也理解不了！其中，我就是一直没搞懂地在使用她。时隔两年，又无意遇到了她，可能是两年的代码经验的积累，有了些新的认识，可以自信的说理解了吧！下面我争取用自己的方式让更多人明白她，而不是背诵她。为了更方便的说明，文章里会自己强加一些概念，只是为了更好的理解，不是什么专业术语之类的。

一、树状数组是干什么的？

平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是 O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是 O(N)，如果实时的对数组进行 M 次修改或求和，最坏的情况下复杂度是 O(MN)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是 O(MlgN)，别小看这个 lg，很大的数一 lg 就很小了，这个学过数学的都知道吧，不需要我说了。申明一下，看下面的文章一定不要急，只需要看懂每一步最后自然就懂了。

二、树状数组怎么干的？

先看两幅图（网上找的，如果雷同，不要大惊小怪～），下面的说明都是基于这两幅图的.

A 图

B 图

是不是很像一颗树？对，这就是为什么叫树状数组了～先看 A 图，a 数组就是我们要维护和查询的数组，但是其实我们整个过程中根本用不到 a 数组，你可以把它当作一个摆设！c 数组才是我们全程关心和操纵的重心。先由图来看看 c 数组的规则，其中 c8 = c4+c6+c7+a8，c6 = c5+a6……先不必纠结怎么做到的，我们只要知道 c 数组的大致规则即可，很容易知道 c8 表示 a1～a8 的和，但是 c6 却是表示 a5～a6 的和，为什么会产生这样的区别的呢？或者说发明她的人为什么这样区别对待呢？答案是，这样会使操作更简单！看到这相信有些人就有些感觉了，为什么复杂度被 lg 了呢？可以看到，c8 可以看作 a1～a8 的左半边和+右半边和，而其中左半边和是确定的 c4，右半边其实也是同样的规则把 a5～a8 一分为二……继续下去都是一分为二直到不能分，可以看看 B 图。怎么样？是不是有点二分的味道了？对，说白了树状数组就是巧妙的利用了二分，她并不神秘，关键是她的巧妙！

她又是怎样做到不断的一分为二呢？说这个之前我先说个叫 lowbit 的东西，lowbit(k) 就是把 k 的二进制的高位 1 全部清空，只留下最低位的 1, 比如 10 的二进制是 1010, 则 lowbit(k)=lowbit(1010)=0010(2 进制)，介于这个 lowbit 在下面会经常用到，这里给一个非常方便的实现方式，比较普遍的方法 lowbit(k)=k&-k，这是位运算，我们知道一个数加一个负号是把这个数的二进制取反+1，如-10 的二进制就是-1010=0101+1=0110，然后用 1010&0110，答案就是 0010 了！明白了求解 lowbit 的方法就可以了，继续下面。介于下面讨论十进制已经没有意义（这个世界本来就是二进制的，人非要主观的构建一个十进制），下面所有的数没有特别说明都当作二进制。

上面那么多文字说 lowbit，还没说它的用处呢，它就是为了联系 a 数组和 c 数组的！ck 表示从 ak 开始往左连续求 lowbit(k) 个数的和，比如 c[0110]=a[0110]+a[0101]，就是从 110 开始计算了 0010 个数的和，因为 lowbit(0110)=0010，可以看到其实只有低位的 1 起作用，因为很显然可以写出 c[0010]=a[0010]+a[0001]，这就为什么我们任何数都只关心它的 lowbit，因为高位不起作用（基于我们的二分规则它必须如此！），除非除了高位其余位都是 0，这时本身就是 lowbit。

既然关系建立好了，看看如何实现a某一个位置数据跟改的，她不会直接改的（开始就说了，a根本不存在），她每次改其实都要维护c数组应有的性质，因为后面求和要用到。而维护也很简单，比如更改了a[0011]，我们接着要修改c[0011],c[0100],c[1000]，这是很容易从图上看出来的，但是你可能会问，他们之间有申明必然联系吗？每次求解总不能总要拿图来看吧？其实从0011——>0100——>1000 的变化都是进行 “去尾” 操作，又是自己造的词–”，我来解释下，就是把尾部应该去掉的 1 都去掉转而换到更高位的 1, 记住每次变换都要有一个高位的 1 产生，所以 0100 是不能变换到 0101 的，因为没有新的高位 1 产生，这个变换过程恰好是可以借助我们的 lowbit 进行的，k +=lowbit(k)。

好吧，现在更新的次序都有了，可能又会产生新的疑问了：为什么它非要是这种关系啊？这就要追究到之前我们说 c8 可以看作 a1～a8 的左半边和+右半边和……的内容了，为什么 c[0011] 会影响到 c[0100] 而不会影响到 c[0101]，这就是之前说的 c[0100] 的求解实际上是这样分段的区间 c[0001]~c[0001] 和区间 c[0011]~c[0011] 的和，数字太小，可能这样不太理解，在比如 c[0100] 会影响 c[1000]，为什么呢？因为 c[1000] 可以看作 0001～0100 的和加上 0101~1000 的和，但是 0101 位置的数变化并会直接作用于 c[1000]，因为它的尾部 1 不能一下在跳两级在产生两次高位 1, 是通过 c[0110] 间接影响的，但是，c[0100] 却可以跳一级产生一次高位 1。

可能上面说的你比较绕了，那么此时你只需注意：c 的构成性质（其实是分组性质）决定了 c[0011] 只会直接影响 c[0100]，而 c[0100] 只会直接影响 [1000]，而下表之间的关系恰好是也必须是 k +=lowbit(k)。此时我们就是写出跟新维护树的代码：

void add(int k,int num)  
{  
    while(k<=n)  
    {  
        tree[k]+=num;  
        k+=k&-k;  
    }  
}  

有了上面的基础，说求和就比较简单了。比如求 0001～0110 的和就直接 c[0100]+c[0110]，分析方法与上面的恰好逆过来，而且写法也是逆过来的，具体就不累述了：

int read(int k)//1~k 的区间和  
{  
    int sum=0;  
    while(k)  
    {  
        sum+=tree[k];  
        k-=k&-k;  
    }  
    return sum;  
}

三、总结一下吧

首先，明白树状数组所白了是按照二分对数组进行分组；维护和查询都是 O(lgn) 的复杂度，复杂度取决于最坏的情况，也是 O(lgn);lowbit 这里只是一个技巧，关键在于明白 c 数组的构成规律; 分析的过程二进制一定要深入人心，当作心目中的十进制。