首页 > 代码库 > [算法 树状数组]

[算法 树状数组]

要学树状数组的先看懂一幅图

技术分享

这就是树状数组的存储方式。

那么树状数组的优点是什么呢,允许任意修改,可快速提取出a数组内数字

 

据图可知

c1=a1,

c2=a1+a2,

c3=a3,

c4=a1+a2+a3+a4,

c5=a5,

c6=a5+a6,

c7=a7,

c8=a1+a2+a3+a4+a5+a6+a7+a8,

c9=a9,

c10=a9+a10,

c11=a11.......

.c16=a1+a2+a3+a4+a5+.......+a16。

分析上面的几组式子可知,当 i 为奇数时,ci=ai ;当 i 为偶数时,就要看 i 的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 c6=a5+a6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 c4=a1+a2+a3+a4(由四向前数四个数的和)。

 

(一)因此得到公式    cn=a(n-a^k+1)+.........+an(其中 k 为 n 的二进制表示中从右往左数的 0 的个数)。

那么,如何求 a^k 呢?求法如下:

 1 int lowbit(int x)

2 {

3     return x&(-x);

4 } 

为啥那?

以68为例,他的二进制是(68)2=1000100. 那么-68呢?因为计算机里的整数采用补码表示(补码是原码取反加一),因此-68实际上是68按位取反,末尾加一以后的结果。如下表(忽略符号位):

原码   1 0 0 0 1 0 0

          ↓

反码   0 1 1 1 0 1 1

         ↓

补码   0 1 1 1 1 0 0

我们把(68)2和(-68)2放在一起看一看:

1 0 0 0 1 0 0

0 1 1 1 1 0 0

发现他们末尾带的0是一样多的。因此lowbit(x)=x&-x.   (&是转换成二进制之后进行与运算;而&&是直接进行与运算)

 

(二)由此,我们就可以求出c数组了

 

1 int sum(int x)
2 {
3     int sum=0;
4     while(x>0)
5     {
6         sum+=c[x];
7         x-=lowbit(x);
8     }
9 }

 

(三)当数组中的元素有变更时,树状数组就发挥它的优势了,算法如下(修改为给某个节点 i 加上 x ):

1 void change(int i,int x)
2 {
3     while(i<=n)
4     {
5         c[i]+=x;
6         i+=lowbit(i)
7     }
8 }

嗯。就这样。不算难。大概就是一种可变更的存储方式吧

 

[算法 树状数组]