【樹狀數組】樹狀數組入門(簡單的原理講解)

看到一個很好的講樹狀數組的部落格，就直接借鑒過來了 ^_^

注明，轉載自 https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html

樹狀數組入門(簡單的原理講解)

樹狀數組可以解決什麼樣的問題：

這裡通過一個簡單的題目展開介紹，先輸入一個長度為n的數組，然後我們有如下兩種操作：

1. 輸入一個數m，輸出數組中下标1~m的字首和
2. 對某個指定下标的數進行值的修改

多次執行上述兩種操作

尋常方法

對于一個的數組，如果需要求1~m的字首和我們可以将其從下标1開始對m個數進行求和，對于n次操作，時間複雜度是O(n^2)，對于值的修改，我們可以直接通過下标找到要修改的數，n次操作時間複雜度為O(n)，在數組n開得比較大的時候，求字首和的效率顯得低了

• 那麼有人提出了一種優化的方式：

  初始我們用一個數組A的儲存每個位置的初始值，然後用一個輔助數組B存放的是下标為i的時候A數組的前i個的和（字首和），那麼當我們需要查詢m個數的字首和的時候隻要直接使用下标對B數組進行查詢即可，n次查詢，時間複雜度為O(n)，而此時，對于單點更新值的維護消耗，由原來的O(n)變成了O(n^2)，因為每一次與更新單點值都會對後面的已經計算好的B數組字首和的值造成影響，需要不斷更新B數組的值，n次更新維護的消耗自然就變成了O(n^2)，更新的效率變得低下

樹狀數組

那麼是否有一種方法可以讓查詢和更新的時間複雜度都小一些呢，至少可以令人接受，這裡将介紹樹狀數組如何處理字首和查詢和單點更新的問題，對于n次操作，時間複雜度都為O(nlogn)

• 借用百度百科上的圖檔

  

  

如圖，對于一個長度為n的數組，A數組存放的是數組的初始值，引入一個輔助數組C（我們通過C數組建立樹狀數組）

C1 = A1

C2 = C1 + A2 = A1 + A2

C3 = A3

C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4

C5 = A5

C6 = C5 + A6 = A5 + A6

C7 = A7

C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

我們稱C[i]的值為下标為i的數所管轄的數的和，C[8]存放的就是被編号8所管轄的那些數的和（有8個），而下标為i的數所管轄的元素的個數則為2^k個（k為i的二進制的末尾0的個數）舉兩個例子查詢下标m8和m5所管轄的數的和

• 8 = 1000，末尾3個0，故k == 3，所管轄的個數為2^3 == 8，C8是8個數的和
• 5 = 0101，末尾沒有0，故k == 0，所管轄的個數為2^0 == 1，C5是一個數的和（它本身A5）

而對于輸入的數m，我們要求編号為m的數的字首和A1~Am（這裡假設樹狀數組已經建立，即C1~C8的值已經求出，别着急，在本文的最下方會做出建立樹狀數組的過程講解，因為現在是在求字首和，就假設C數組已經可用了吧）舉兩個例子m7和m6（sum(i)表示求編号為i的字首和）

• m==7 sum(7) = C7 + C6 + C4

  那麼我們是怎麼得到編号7是由哪幾個C[i]求和得到呢（C4, C6, C7怎麼得到的），這裡有介紹一種巧妙的方法：

  對于查詢的m，将它轉換成二進制後，不斷對末尾的1的位置進行-1的操作，直到全部為0停止

  7的二進制為0111（C7得到），那麼先對0111的末尾1的位置-1，得到0110 == 6（C6得到），再對0110末尾1位置-1，得到0100 == 4（C4得到），最後對0100末尾1位置-1後得到0000（結束信号），計算停止，至此C7，C6，C4全部得到，求和後就是m == 7時它的字首和

• m==6 sum(6) = C6 + C4

  m == 6時也是一樣，先轉成2進制等于0110，經過兩次變換後為0100（C4）和0000（結束信号），那麼求和後同樣也得到了預計的結果

這裡要介紹一個高效的方法，lowbit(int m)，這是一個函數，它的作用是求出m的二進制表示的末尾1的位置，對于要查詢m的字首和，m = m - lowbit(m)代表不斷對二進制末尾1進行-1操作，不斷執行直到m == 0結束，就能得到字首和由哪幾個Cm構成，十分巧妙，lowbit也是樹狀數組的核心

int lowbit(int m){
    return m&(-m);
}
           

關于m&(-m)很多童鞋可能感到困惑，那麼就不得不提及一下負數在計算機記憶體中的存儲形式，負數在計算機中是以補碼的形式存儲的，如13的二進制表示為1101，那麼-13的二進制而将13二進制按位取反，然後末尾+1，即0010 + 0001 = 0011，那麼1101 & 0011== 0001，很顯然得到m == 13二進制末尾1的位置是2的0次方位，将13 - 0001 == 12，再對12執行lowbit操作，1100 & 0100 == 0100，也很輕易得到了m == 12時二進制末尾1的位置是2的2次方位，将12 - 0100 == 8，再對8執行lowbit操作，0100 & 1100 == 0100，得到m == 8時二進制位是2的2次方位，8 - 0100 == 0（結束操作），通過循環得到的13，12，8，則sum(13) == C13 + C12 + C8

求字首和的代碼

int ans = 0;
int getSum(int m){
    while(m > 0){
        ans += C[m];
        m -= lowbit(m);
    }
}
           

對于n次字首和的查詢，時間複雜度為O(nlogn)

接下來講解單點更新值

對于輸入編号為x的值，要求為它的值附加一個value值，我們把圖再一次拿下來

假設x2，value5，那麼我們先找到A[2]的位置，通過觀察我們得知，如果修改了A[2]的值，那麼管轄A[2]的C[2]，C[4]，C[8]的字首和都要加上value（所有的祖先節點），那麼和查詢類似，我們如何得到C2的所有祖先節點呢（因為C2和A2的下标相同是以更新時查詢從C[x]開始），依舊是上述的巧妙的方法，但是我們把它倒過來

對于要更新x位置的值，我們把x轉換成二進制，不斷對二進制最後一個1的位置+1，直到達到數組下标的最大值n結束

• 對于給出的例子x2，假設數組下标上限n8，x轉換成二進制後等于0010（C2），對末尾1的位置進行+1，得到0100（C4），對末尾的1的位置進行+1，得到1000（C8），循環結束，對C2，C4，C8的字首和都要加上value，當然不能忘記對A[2]的值+value，單點更新值過程結束

給出代碼

void update(int x, int value){
    A[x] += value;    //不能忘了對A數組進行維護，盡善盡美嘛
    while(x <= n){
        C[x] += value;
        x += lowbit(x);
    }
}
           

對于n次更新操作，時間複雜度同樣為O(nlogn)

這裡有一個注意事項，我們對于求字首和與單點更新時，樹狀數組C是拿來直接使用的，那麼問題來了，樹什麼時候建立好的，我怎麼不知道？?

事實上，對于一個輸入的數組A，我們一次讀取的過程，就可以想成是一個不斷更新值的過程（把A1~An從0更新成我們輸入的A[i]），是以一邊讀入A[i]，一邊将C[i]涉及到的祖先節點值更新，完成輸入後樹狀數組C也就建立成功了

• 完整代碼如下：

#include<stdio.h>
#include<string.h>

int a[10005];
int c[10005];
int n;

int lowbit(int x){
	return x&(-x);
}

int getSum(int x){
	int ans = 0;
	while(x > 0){
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}

void update(int x, int value){
	a[x] += value;
	while(x <= n){
		c[x] += value;
		x += lowbit(x);
	}
}

int main(){
	while(scanf("%d", &n)!=EOF){	//用于測試n == 8 
		memset(a, 0, sizeof(a));
		memset(c, 0, sizeof(c));
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);		//a[i]的值根據具體題目自己安排測試可以1，2，3，4，5，6，7，8 
			update(i, a[i]);		//輸入的過程就是更新的過程 
		}
		int ans = getSum(n-1);		//用于測試輸出n-1的字首和 輸出28 
		printf("%d\n", ans);
	}	
	return 0;
}