树状数组——二进制和区间相关计算的巧妙结合

前言

  在数组,我们常常会遇上区间求和相关的问题,即求数组A中第i个元素到第j个元素(i<j)之和。

  这个问题看起来比较简单,只需要累加即可:

$$Sum(i,j) = A[i]+A[i+1]+...+A[j]$$

  但是在面对大数据量的时候,它的时间复杂度也很高,而且如果需要进行多次查询,我们可能会进行大量重复的计算,这时一种效率上的浪费。

  那有的同学可能会想到,如果要区间求和,可以使用前缀和数组啊,我们用S[i]记录第一个元素到第i个元素之和,那么做差不就可以得到区间和了吗?

$$Sum(i,j) = S[j]-S[i-1]$$

  如果这个数组是一个常量,那么用前缀和数组确实完事大吉了,可是万一数组要更新呢,假如元素A[x]要更新,那个从第x个元素开始,所有S数组的值都要改变,这又带来了很多时间上的开销。相比之下,前一种方法就简单多了,只需要更新A[x]即可。

  区间求和 更新元素
累加求和 O(n) O(1)
前缀数组 O(1) O(n)

   由此可见,累加求和和前缀和数组各有缺陷,我们需要一种新的数据结构和算法,既能高效地查询区间之和,更新元素时又比较方便。于是乎,树状数组就出现了。

  树状数组是被应用于区间相关计算的经典数据结构,它巧妙地运用了二进制,提升了区间求和,元素更新的效率。

树状数组和二进制

   设树状数组为C,其元素C[i]和前缀和数组S[i]一样,记录的也是到第i个元素为止,原数组部分元素的和,但是到底是几个元素的和,就要看i的二进制表示了。我们要找到下标转化为二进制中最后一个1位置,以此来确定树状数组所覆盖的原数组的长度,所以也可以看出,C[i]所覆盖数组的长度,也就是能整除i的最大2的幂次。这么说可能比较抽象,我们来举几个例子,假设树状数组为C,求C[14],C[15],C[16]各自覆盖的元素的长度,现将其转化为二进制:

树状数组——二进制和区间相关计算的巧妙结合

14最后一个1出现在倒数第二位,那么它覆盖的原数组的长度就是2^1 = 2,15最后一个1出现在倒数第一位,那么它覆盖的原数组的长度就是2^0 = 1,16最后一个1出现在第一位,那么它覆盖的原数组的长度就是2^5 = 16。

用一张图来比较树状数组和原数组

树状数组——二进制和区间相关计算的巧妙结合

区间求和

  从上图可以看见,树状数组通过二进制,用一个数组表示多个不同长度的部分和。这样,在计算前缀和时,只需要挑选合适的值组合在一起就好了,例如,前11个元素之和即为:

 $$Sum(1,11) = C[11]+C[10]+C[8]$$

  如果采用累加求和的方式,需要进行10次加法运算,但是使用树状数组,就只需要两次加法运算,计算量大大降低了,如果要求区间之和,只需要求前缀和之差就可以了。

单点更新

当原数组元素更新时,树状数组的对应元素也要跟着一同更新,但它和前缀和不同,只需要更新部分值。 具体来说,就是树状数组中那些涵盖了更新元素的值。例如,当原数组A[5]更新时,涵盖它的C[5],C[6],C[8],C[16]都要同步更新。同用是更新,前缀和数组需要更新12个元素。

 

代码实现

从之前的分析可以看出,使用树状数组可以同时提高区间求和和单点更新的效率,但是我们还有很多细节性的问题没有解决,其中最重要的就是两点:

  • 更新原数组时,树状数组中哪些元素要跟着更新呢?
  • 区间求和时,该如何选择对应的元素呢?

下面就来揭晓这些问题的答案。首先,回到最初的问题,假设数组下标为x,我们说要找到x二进制中最后一个1的位置,以确定树状数组所覆盖的部分和长度,这该如何实现呢?这里其实要用到位运算,设lowbit(x)为取x最后一个1对应的2的幂次,有:

$ lowbit(x) = x&(-x) $

 在计算机中,整数x取反相当于把x二进制的每一位都取反,然后加1,所以-x和x的最后一个1的位置相同,其他所有1的位置均不同,然后两者按位与,即可得到最后一个1的位置:

树状数组——二进制和区间相关计算的巧妙结合

 确定了这个最低位1的位置,问题就清晰很多了,我们知道,C[i]代表到A[i]为止之前(包括A[i]),lowbit(i)个元素之和。这样就可以将A[i]至A[i]之和分为两部分,从而可以缩小问题规模:

$$Sum(1,i) = Sum(1,i-lowbit(i))+C[i]$$

 对应的代码也不难得到:

1 int getSum(int x){
2     int sum = 0;
3     for(int i=x;i>0;i-=lowbit(i)){
4         sum+=C[i];
5     }
6     return sum;
7 }

求区间和Sum(i,j),只要作差即可:

$$Sum(i,j) = Sum(1,j)-Sum(1,i-1)$$

下面解决另一个关键问题,当原数组A有元素更新时,树状数组C要如何更新呢?很明显,当A[i]更新时,C必定是从C[i]处开始更新(C[i]之前没有覆盖到A[i])。如果C[i]被更新,那么之后i之后,覆盖C[i]的元素也一定会更新,实际上,这种更新时逐层的,例如更新C[3]会导致C[4]更新,C[4]更新导致C[8]更新。因此,若已知C[i]被更新,则C中下一个被更新的元素是离C[i]最近,覆盖了C[i]的值。设这个元素在i之后第a位,即C[i+a],若C[i+a]可以覆盖C[i]中的元素,则必须满足,C[i+a]覆盖的第一个A中元素的下标小于等于都C[i]覆盖的第一个A中元素的小标,即:

$$i+a-lowbit(i+a)<=i-lowbit(i)\\a<=lowbit(i+a)-lowbit(i)$$

这样,该问题就变成了,求满足上式最小的a。

思考lowbit函数的定义,我们可以发现,a不可能比lowbit(i)小,否则i+a二进制中最后一个1的位置一定在中最后一个1的后面,lowbit(i+a)-lowbit(i)<0。那a可以取lowbit(i)吗,可以的。因为i+lowbit(i)最后一个1的位置相同,两种相加会导致进位,只要进位,就等于两个lowbit(i)之和了,所以

$$lowbit(i)<=lowbit(i+a)-lowbit(i)\\lowbit(i)+lowbit(i)<=lowbit(i+lowbit(i))$$

所以a取lowbit(i)。

更新代码如下:

1 void updata(int x,int v)  //将第x个整数加上v
2 {
3     for(int i=x;i<=N;i+=lowbit(i)){
4         c[i]+=v;
5     }
6 }

 

 

上一篇:.Net程序员学用Oracle系列(6):表、字段、注释、约束、索引


下一篇:手游:cocos2d-x3.0 移植 wp8 开发 各种 “蛋疼”问题的汇总