大佬博客链接

第一篇是搜索树状数组第一篇被许多人称赞的博客，通过这篇博客可以很好的理解lowbit。

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

       平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是O(M*lgN)，别小看这个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)。此时我们就是写出跟新维护树的代码：

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

1. int read(int k)//1~k的区间和  
2. {  
3.     int sum=0;  
4.     while(k)  
5.     {  
6.         sum+=tree[k];  
7.         k-=k&-k;  
8.     }  
9.     return sum;  
10. }  

三、总结一下吧

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

看完那一篇我有一点懂了，但还是有些懵懂，再看完下面这一篇树桩数组单点更新就都会了。。。下面还有二维树桩数组。。

第01讲 什么是树状数组？

树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。

有些同学会觉得很奇怪。用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？

但是，如果题目的A[]会改变呢？例如：

我们来定义下列问题：我们有n个盒子。可能的操作为

1.向盒子k添加石块

2.查询从盒子i到盒子j总的石块数

自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。但是用树状数组，对操作1和2的时间复杂度都为O(logn)。

第02讲 图解树状数组C[]

现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]

 

网络上面都有这个图，但是我将这个图做了2点改进。

（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。

（2）C[i]为A[i]对应的那一列的最高的节点。

现在告诉你：序列C[]就是树状数组。

那么C[]如何求得？

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：

因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。

现在不得不引出关于二进制的一个规律：

先仔细看下图：

将十进制化成二进制，然后观察这些二进制数最右边1的位置：

1 --> 00000001

2 --> 00000010

3 --> 00000011

4 --> 00000100

5 --> 00000101

6 --> 00000110

7 --> 00000111

8 --> 00001000

1的位置其实从我画的满二叉树中就可以看出来。但是这与C[]有什么关系呢？

接下来的这部分内容很重要：

在满二叉树中，

以1结尾的那些结点（C[1],C[3],C[5],C[7]），其叶子数有1个，所以这些结点C[i]代表区间范围为1的元素和；

以10结尾的那些结点（C[2],C[6]），其叶子数为2个，所以这些结点C[i]代表区间范围为2的元素和；

以100结尾的那些结点（C[4]），其叶子数为4个，所以这些结点C[i]代表区间范围为4的元素和；

以1000结尾的那些结点（C[8]），其叶子数为8个，所以这些结点C[i]代表区间范围为8的元素和。

扩展到一般情况：

i的二进制中的从右往左数有连续的x个“0”，那么拥有2^x个叶子，为序列A[]中的第i-2^x+1到第i个元素的和。

终于，我们得到了一个C[i]的具体定义：

C[i]=A[i-2^x+1]+…+A[i]，其中x为i的二进制中的从右往左数有连续“0”的个数。

第03讲 利用树状数组求前i个元素的和S[i]

理解了C[i]后，前i个元素的和S[i]就很容易实现。

从C[i]的定义出发：

C[i]=A[i-2^x+1]+…+A[i]，其中x为i的二进制中的从右往左数有连续“0”的个数。

我们可以知道：C[i]是肯定包括A[i]的，那么：

S[i]=C[i]+C[i-2^x]+…

也许上面这个公式太抽象了，因为有省略号，我们拿一个具体的实例来看：

S[7]=C[7]+C[6]+C[4]

因为C[7]=A[7]，C[6]=A[6]+A[5]，C[4]=A[4]+A[3]+A[2]+A[1]，所以S[7]=C[7]+C[6]+C[4]

（1）i=7，求得x=0，那么我们求得了A[7]；

（2）i=i-2^x=6，求得x=1，那么求得了A[6]+A[5]；

（3）i=i-2^x=4，求得x=2，那么求得了A[4]+A[3]+A[2]+A[1]。

讲到这里其实有点难度，因为S[i]的求法，如果要讲清楚，那么得写太多的东西了。所以不理解的同学，再反复多看几遍。

从（1）（2）（3）这3步可以知道，求S[i]就是一个累加的过程，如果将2^x求出来了，那么这个过程用C++实现就没什么难度。

现在直接告诉你结论：2^x=i&(-i)

证明：设A’为A的二进制反码，i的二进制表示成A1B，其中A不管，B为全0序列。那么-i=A’0B’+1。由于B为全0序列，那么B’就是全1序列，所以-i=A’1B，所以：

i&(-i)= A1B& A’1B=1B，即2^x的值。

所以根据（1）（2）（3）的过程我们可以写出如下的函数：

int Sum(int i) //返回前i个元素和

{

       int s=0;

       while(i>0)

       {

              s+=C[i];

              i-=i&(-i);

       }

       return s;

}

第04讲 更新C[]

正如第01讲提到的小石块问题，如果数组A[i]被更新了怎么办？那么如何改动C[]？

如果改动C[]也需要O(n)的时间复杂度，那么树状数组就没有任何优势。所以树状数组在改动C[]上面的时间效率为O(logn)，为什么呢？

因为改动A[i]只需要改动部分的C[]。这一点从第02讲的图中就可以看出来：

如上图：

假如A[3]=3，接着A[3]+=1，那么哪些C[]需要改变呢？

答案从图中就可以得出：C[3],C[4],C[8]。因为这些值和A[3]是有联系的，他们用树的关系描述就是：C[3],C[4],C[8]是A[3]的祖先。

那么怎么知道那些C[]需要变化呢？

我们来看“A”这个结点。这个“A”结点非常的重要，因为他体现了一个关系：A的叶子数为C[3]的2倍。因为“A”的左子树和右子树的叶子数是相同的。 因为2^x代表的就是叶子数，所以C[3]的父亲是A，A的父亲是C[i+2^0]，即C[3]改变，那么C[3+2^0]也改变。

我们再来看看“B”这个结点。B结点的叶子数为2倍的C[6]的叶子数。所以B和C[6+2^1]在同一列，所以C[6]改变，C[6+2^1]也改变。

推广到一般情况就是：

如果A[i]发生改变，那么C[i]发生改变，C[i]的父亲C[i+2^x]也发生改变。

这一行的迭代过程，我们可以写出当A[i]发生改变时，C[]的更新函数为：

void Update(int i,int value)  //A[i]的改变值为value

{

       while(i<=n)

       {

              C[i]+=value;

              i+=i&(-i);

       }

}

另一个博客关于k的补充：

现在我们再来理解一个知识：

k 表示的 为i 这个节点表示的树的深度。

为什么呢？

我们知道k为i的末尾0的个数，而小于i的节点的值肯定要小于i，那么它们的k绝对要小于i的k，而最长的就是k，因为它的二进制表示的数只能允许它右移k位，右移k位之后它就是叶子节点了，就只表示一个单一的A[]数组的值了，同时也是C[]树状数组的值。

 

有了这点知识为基础，那么我们就可以知道，我们要修改某个元素的值，就会修改C[]的值，以及它的所有祖先节点的值。

而我们已经知道，它的父节点的节点编号就是i + lowbit[i],一步就可以返回过去，而这个树的深度只有logn，所以我们往上一步一步的修改它的祖先节点就行了，且最多只要logn步，因此时间复杂度是O(logn)。

第05讲 一维树状数组的应用举例

废了4讲的话，我们终于把一维树状数组的2个不到5行的代码给搞定了。现在要正式投入到应用当中。

题目链接：http://poj.org/problem?id=2352

题意：按照y升序给你n个星星的坐标，如果有m个星星的x,y坐标均小于等于星星A的坐标，那么星星A的等级为m。

分析：是一道树状数组题。举例来说，以下是题目的输入：

5

1 1

5 1

7 1

3 3

5 5

由于y坐标是升序的且坐标不重复，所以在星星A后面输入的星星的x,y坐标不可能都小于等于星星A。假如当前输入的星星为（3,3），易得我们只需要去找 树状数组中小于等于3的值就可以了，即GetSum(3)。注意：A[i]表示x坐标为i的个数，C[]为A[]的树状数组，那么GetSum(i)就是 序列中前i个元素的和，即x小于等于i的星星数。

本题还是一点要注意：星星坐标的输入可以是（0,0），所以我们把x坐标统一加1，然后用树状数组实现。

第06讲 二维树状数组

BIT可用为二维数据结果。假设你有一个带有点的平面(有非负的坐标)。你有三个问题：

1.在(x , y)设置点

2.从(x , y)移除点

3.在矩形(0 , 0), (x , y)计算点数 - 其中(0 , 0)为左下角，(x , y)为右上角，而边是平行于x轴和y轴。

对于1操作，在（x,y）处设置点，即Update(x,y,1)，那么这个Update要怎么写？很简单，因为x，y坐标是离散的，所以我们分别对x,y进行更新即可，函数如下：

void Update(int x,int y,int val)

{

       while(x<=n)

       {

              int y1=y;

              while(y1<=n)

              {

                     C[x][y1]+=val;

                     y1+=y1&(-y1);

              }

              x+=x&(-x);

       }

}

那么根据Update可以推得：GetSum函数为：

int GetSum(int x,int y)

{

       int sum=0;

       while(x>0)

       {

              int y1=y;

              while(y1>0)

              {

                     sum+=C[x][y1];

                     y1-=y1&(-y1);

              }

              x-=x&(-x);

       }

       return sum;

}

第07讲 二维树状数组的应用举例

题目链接：http://poj.org/problem?id=2155

我们先讨论POJ2155的一维情况，如下：

有一个n卡片的阵列。每个卡片倒放在桌面上。你有两个问题：

  1. T i j (反转从索引i到索引j的卡片，包括第i张和第j张卡——面朝下的卡将朝上；面朝上的卡将朝下)

  2. Q i (如果第i张卡面朝下回答0否则回答1)

解决：

解决问题(1和2)的方法有时间复杂度O(log n)。在数组f(长度n + 1)我们存储每个问题T(i, j)——我们设置f[i]++和f[j + 1]--。对在i和j之间(包括i和j)每个卡k求和f[1] + f[2] + ... + f[k]将递增1，其他全部和前面的一样(看图2.0清楚一些)，我们的结果将描述为和(和累积频率一样)模2。

图 2.0

使用BIT来存储(增加/减少)频率并读取累积频率。

理解了一维的情况，POJ2155就是其二维的版本，易得只需要更(x1,y1)，(x1,y2+1)，(x2+1,y1)，(x2+1,y2+1)四个点的C[]的值就可以了，最后的结果依然是GetSum(x,y)%2

这里可能你对二维树状数组还是不懂，下面这篇博客做了很好的解释：

如果是二维的树状数组的话,心里思考一下,是不是感觉很眼熟哦!
其实他们的原理是一样的：
设二维数组为：
a[][]={{a11,a12,a13,a14,a15,a16,a17,a18},
{a21,a22,a23,a24,a25,a26,a27,a28},
{a31,a32,a33,a34,a35,a36,a37,a38},
{a41,a42,a43,a44,a45,a46,a47,a48}};
那么C[1][1] = a11,C[1][2] = a11 + a12;
如此当C[1][i]...C[1][j]时跟一维的树状数组是没有什么区别的
那么C[2][1] = a11 + a21,C[2][2] = a11 + a12 + a21 + a21,如此可以发现
其实C[2][i].....C[2][j],就是C[1][],C[2][],单独的两个一维树状数组同一位置的值合并在一起
而C[3][1] = a31,C[3][2] = a31 + a32......
而C[4][1] = a11 + a21 + a31 + a41,C[4][2] = a11 + a12 + a21 + a22 + a31 + a32 + a41 + a42
有没有发现，如果单独把二维中的第一个维度拿出来A[1][m] + A[2][m] = C[2][m],A[3][m] = C[3][m],
是不是也和一维的数组一样,所以二维数组的规律就是,不管是横坐标还是纵坐标,将他们单独拿出来,他们
都符合x += lowbit(x),属于它的父亲节点.

如此二维数组的单点更新代码如下:

这就是二维树状数组的成型,那么三维以及以上呢,想来大家都已经秒懂了,是的,没错,就是在最外一层加个循环跟一维变为二维原理一样；

然后就是树状数组也可以跟线段树一样进行区间更新的，下面是几篇比较好的博客汇总：

第一篇：

对一段区间每个值加上一个val如何处理呢？ 
假设存在一个数组add[]，add[x] = val 表示把[x,n]这个区间每个元素+val. 
这样当我们把[x,y]区间每个元素都+val的时候，把问题转化为把[x,n]的区间每个元素+val，把[y+1,n]每个元素-val 
这样当我们查询[1,x]区间的区间和时，实际的 
sum[x] = A[1] + A[2] +… + A[x] + add[1] * (x+1-1) + add[2] * (x+1-2) + … + add[x] * (x+1-x) = (A[1] + A[2] + … + A[x]) + (x+1)(add[1] + add[2] + …+ add[x] ) - (1 * add[1] + 2*add[2] + …+x *add[x])

第二篇：

而对于区间增加以及减少做个简单的解答:

对于树状数组，只能够提供区间修改（增加或者是减少d），最后单点求值
首先讲一下所谓的区间修改，他的本质其实还是单点修改，因为树状数组基本提供的功能就是两个
一个是单点修改，一个是区间求值，所以区间修改以及单点求值的本质还是树状数组的两个基本功能
首先是区间修改对应的树状数组的功能是单点修改，通过修改单个点的值来修改整个区间
而怎样通过单个点的修改来表示修改了整个区间呢?
首先我们要理解一个思维就是区间修改的思维方式与之前的树状数组的表达方式不相同了，
首先说明C[i]求解与树状数组肯定没有什么区别，但是sum[i]表示的却是i这个点的值，
为什么，因为此时的A[1],A[2]....A[m]表示不是他的值，在以往的树状数组中，他都是表示
位于数组1位置的值，位于数组2位置的值....位于数组m位置的值，
但是此时，他们只是一个值的一部分，此刻，有些人想不明白了，什么叫做一个值得一部分
其实是这样的,原本A[m]的值被分解了，分解成了A[m] = A[m - lowbit(m)] + A[m - lowbit(m) - lowbit(m - lowbit(m))] + .....
如此,所谓的C[m]表示的只是前辍和的一部分，如图解:  //着重理解下这里，自己举个例子手动运算下

如此，如果要区间修改，单点求值的话，前提必须是初始条件能够满足构成前缀和
我们要改变一个区间[a , b]的值，让他们加一的话先是[a .... N] + 1为什么，这就是往后更新
然后是[b .... N] - 1即可,如此通过上图可以知道B[i]表示i点的值,他的值是通过A[1 . . . i]的前缀和得来的
如此我们只要在C[i]处+ 1,那么通过前辍和可以知道，后面的数已经在这个数加一的基础都加了个一，他们的值已经表示为了一个区间内变化
当然这种变化是从i....N这个区间都变化了，所以还要讲[b ,,,, N]变回来就可以了
如此可以明白通过求和可以得到i这个点的值(B[i])因为求和的含义就是代表i点这个数的值.

第三篇：区间更新区间求和：

 树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值，查询只能查数组的前缀和，

但这个题目求的是某一区间的数组和，而且要支持批量更新某一区间内元素的值，怎么办呢？实际上，

还是可以把问题转化为求数组的前缀和。

 

    首先，看更新操作update(s, t, d)把区间A[s]...A[t]都增加d，我们引入一个数组delta[i]，表示

A[i]...A[n]的共同增量，n是数组的大小。那么update操作可以转化为：

1）令delta[s] = delta[s] + d，表示将A[s]...A[n]同时增加d，但这样A[t+1]...A[n]就多加了d，所以

2）再令delta[t+1] = delta[t+1] - d，表示将A[t+1]...A[n]同时减d

 

    然后来看查询操作query(s, t)，求A[s]...A[t]的区间和，转化为求前缀和，设sum[i] = A[1]+...+A[i]，则

                            A[s]+...+A[t] = sum[t] - sum[s-1]，

那么前缀和sum[x]又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始

值保存在数组org中，并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i)，那么

                            sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1

                                         = org[1]+...+org[x] + segma(delta[i]*(x+1-i))

                                         = segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)，1 <= i <= x

这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和

delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。

poj3469 题目链接：http://poj.org/problem?id=3468

最后提供所有树状数组的模板：

14、树状数组
（1）、单点增减+区间求和
思路：C[x]表示该点的元素:sum(x)=C[1]+C[2]+……C[x]

（2）、区间增减+单点查询

思路：C[x]表示该点元素与左边元素的差值:num[x]=C[1]+C[2]+……C[x]

（3）、区间增减+区间查询

思路：C1[x]表示该点元素与左边的差值，C2[x]表示的是x*C[x]

则可以想到用C1[x]维护C[x]的值,C2[x]维护x*C[X]的值

15、多维树状数组
①单点增减（add） + 矩形求和（query） 

②矩形增减（update） + 单点求值（sum）

③矩形增减（update）+ 矩形求和（query）


④单点增减（add） + 立方体求和（query）

⑤立方体增减（update） + 单点求值（sum）

⑥立方体增减（update） + 立方体求和（query）///随便写写……复杂度较高

 

16、树状数组—区间最大值