首页 > 代码库 > Binary_Indexed_Tree (BIT)

Binary_Indexed_Tree (BIT)

树状数组

树状数组:

是一种设计新颖的数组结构,它能够高效地获取数组中连续n个数的和。

线性结构只能逐个扫描元素,而树状结构可以实现跳跃式扫描。

概括说:

树状数组通常用于解决以下问题:

数组{a}中的元素可能不断地被修改,怎样才能快速地获取连续几个数的和?

 

一般讲到树状数组都会少不了下面这个图:

技术分享

 

下面来解析该图,找出其中的规律:

据图可知:

c1 = a1

c2 = 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

 

分析上面的几组式子可知:

当i为奇数时

  ci = ai

当i为偶数时

  就要看i的因子中最多有2的多少次幂。

For Example:

6的因子中有2的一次幂,等于2。所以 c6 = a5 + a6 (由6向前数两个数的和)。

4的因子中油2的二次幂,等于4。所以 c4 = a1 + a2 + a3 + a4 (由4向前数四个数字的和)。

 

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

  那么如何求 a^k 呢?

  求法如下:

  技术分享
1 int lowbit(int x)2 {3     return x & (-x);4 }
View Code

    lowbit () 的返回值就是 2^k 次方的值。

  求出来 2^k 之后,数组 c 的值也就都出来。

  接下来我们要求数组中所有元素的和。

二、求数组的和的算法如下:

  ① 令sum = 0,转向第②步;

  ② 接下来判断,如果 n > 0 的话,就令sum = sum + cn 转向第③步,否则的话,终止算法,返回sum的值;

  ③ n = n - lowbit(n) (将n的二进制表示的最后一个0删掉),返回第二步。

  技术分享
 1 int sum(int n) 2 { 3     int sum = 0; 4     while (n > 0) 5     { 6         sum+=c[n]; 7         n = n - lowbit(n); 8     } 9     return sum;       10 }
View Code

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

  ① 当 i < n 时,执行下一步;否则的话,算法结束;

  ② ci = ci + x, i = i + lowbit (i) (在 i 的二进制表示的最后加0);返回第 ① 步。

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

 

Binary_Indexed_Tree (BIT)