BIT 樹狀數組詳解及例題

（一）樹狀數組的概念

如果給定一個數組，要你求里面所有數的和，一般都會想到累加。但是當那個數組很大的時候，累加就顯得太耗時了，時間復雜度為O(n)，并且采用累加的方法還有一個局限，那就是，當修改掉數組中的元素后，仍然要你求數組中某段元素的和，就顯得麻煩了。所以我們就要用到樹狀數組，他的時間復雜度為O（lgn），相比之下就快得多。下面就講一下什么是樹狀數組：

一般講到樹狀數組都會少不了下面這個圖：

下面來分析一下上面那個圖看能得出什么規律：

據圖可知：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) //取x的最低位1，比如4，則返回4，如5，則返回1
2 {
3     return x&(-x);
4 }

View Code

lowbit（）的返回值就是 2^k 次方的值。

求出來 2^k 之后，數組 c 的值就都出來了，接下來我們要求數組中所有元素的和。

（二）求數組的和的算法如下：

（1）首先，令sum=0，轉向第二步；

（2）接下來判斷，如果 n>0 的話，就令sum=sum+cn轉向第三步，否則的話，終止算法，返回 sum 的值；

（3）n=n - lowbit（n）（將n的二進制表示的最后一個零刪掉），回第二步。

代碼實現：

 1 int Sum(int i)   //求前i項的和
 2 {
 3     int s = 0;
 4     //將前i項分段
 5     while(i > 0)
 6     {
 7         s += sum[i];
 8         i -= lowbit(i);  //去掉i的二進制最后一個
 9     }
10     return s;
11 }

View Code

（三）當數組中的元素有變更時，樹狀數組就發揮它的優勢了，算法如下（修改為給某個節點 i 加上 x ）：

（1）當 i<=n 時，執行下一步；否則的話，算法結束;

（2）ci=ci+x ，i=i+lowbit（i）（在 i 的二進制表示的最后加零），返回第一步。

代碼實現：

1 void update(int i, int val)  //將第i個元素增加val
2 {
3     //i的祖先都要增加val
4     while(i <= n)
5     {
6         sum[i] += val;
7         i += lowbit(i);   //將i的二進制未位補為得到其祖先
8     }
9 }

View Code

（二）樹狀數組的應用

以下數組下標均默認從1開始

應用一

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左邊)小于等于a[i]的數的個數。對此例b[] = {0,1,1,2,0}。那么該如何去求得b[i]呢？

解法：假如要得到b[4]的值,對于a[4] = 4. 我們只要得到在a[1],a[2],a[3] 中出現小于等于4的個數，即1,2,3,4的個數,此例即為2. a[1] = 2 < a[4], a[3] = 3 < a[4]. 所以b[4] = 2;其他的以此類推. 求b[i]的值，需要得到在a[1],a[2]....a[i-1]中出現小于等于a[i]的個數，即1,2...a[i]的個數. 相當于求前a[i]項的和，可用到樹狀數組.

具體操作

for(int i=1; i<=n; i++)

{

b[i] = getSum(a[i]); //求前a[i]項的和

update(a[i],1); //第a[i]個元素+1

}

應用二

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左邊)大于等于a[i]的數的個數。對此例b[] = {0,0,1,1,4}。那么該如何去求得b[i]呢？

解法1: 只需要先將數組a倒過來編號，即將a轉換為，a[] ={4,1,3,2,5}.此時具體的操作如應用一

以下數組下標均默認從1開始

應用一

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左邊)小于等于a[i]的數的個數。對此例b[] = {0,1,1,2,0}。那么該如何去求得b[i]呢？

解法：假如要得到b[4]的值,對于a[4] = 4. 我們只要得到在a[1],a[2],a[3] 中出現小于等于4的個數，即1,2,3,4的個數,此例即為2. a[1] = 2 < a[4], a[3] = 3 < a[4]. 所以b[4] = 2;其他的以此類推. 求b[i]的值，需要得到在a[1],a[2]....a[i-1]中出現小于等于a[i]的個數，即1,2...a[i]的個數. 相當于求前a[i]項的和，可用到樹狀數組.

具體操作

for(int i=1; i<=n; i++)

{

b[i] = getSum(a[i]); //求前a[i]項的和

update(a[i],1); //第a[i]個元素+1

}

應用二

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左邊)大于等于a[i]的數的個數。對此例b[] = {0,0,1,1,4}。那么該如何去求得b[i]呢？

解法1: 只需要先將數組a倒過來編號，即將a轉換為，a[] ={4,1,3,2,5}.此時具體的操作如應用一

解法2:改變更新路徑和求和路徑

 1 void update(int x, int val)
 2 {
 3     for(int i=x; i>0; i-=lowbit(i))
 4     {
 5         sum[i] += val;
 6     }
 7 }
 8 
 9 int getSum(int x)
10 {
11     int s = 0;
12     for(int i=x; i<MAXN; i+=lowbit(i))
13     {
14         s += sum[i];
15     }
16     return s;
17 }

View Code

應用三逆序數

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[i],a[i+1]...a[n]中(即位置i的右邊)小于等于a[i]的數的個數。對此例b[] = {1,3,1,1,0}。那么該如何去求得b[i]呢？

操作：應用一位置i的左邊，應用三是位置i的右邊。然后只需要在應用一的基礎上從后往前操作即可

1 for(int i=n; i>=1; i--)
2 
3 {
4 
5 b[i] = getSum(a[i]); //求前a[i]項的和
6 
7 update(a[i],1);      //第a[i]個元素+1
8 
9 }

View Code

應用四

假如給你一個數組a[ ] = {2,5,3,4,1},求b[i]，b[i] 表示在a[i],a[i+1]...a[n]中(即位置i的右邊)大于等于a[i]的數的個數。對此例b[] = {3,0,1,0,0}。那么該如何去求得b[i]呢？

操作：只需將數組a倒過來編號,即將a轉化為 a[]={4,1,3,2,5} 然后利用應用三

二維樹狀數組

 1 int lowbit(int x)
 2 {
 3     return x&(-x);
 4 }
 5 
 6 void update(int x, int y, int val) //將 a[x][y] 的值增加val
 7 {
 8     for(int i=x; i<N; i+=lowbit(i))
 9     {
10         for(int j=y; j<N; j+=lowbit(j))
11         {
12             sum[i][j] += val;
13         }
14     }
15 }
16 
17 
18 int getSum(int x, int y) //求以1,1為左上角端點,學校，x,y為右下角端點的矩陣和.
19 {
20     int s = 0;
21     for(int i=x; i>0; i-=lowbit(i))
22     {
23         for(int j=y; j>0; j-=lowbit(j))
24         {
25             s += sum[i][j];
26         }
27     }
28     return s;
29 }