單點更新，區(qū)間查詢

假設有一個數(shù)組，對他大量的修改和查詢，修改的是數(shù)組中某一個元素的值，查詢的是數(shù)組中任意一個區(qū)間的和。對于修改比較簡單，時間復雜度是 O(1) ，而查詢的時間復雜度是 O(n) 。有同學可能會說使用前綴和來優(yōu)化，前綴和查詢的時間復雜度確實是 O(1) ，但如果我們修改某一個元素的時候，前綴和后面的值也都要修改，時間復雜度是 ?O(n) 。那么我們綜合一下，有沒有一種方式可以讓修改和查詢時間復雜度降一個數(shù)量級呢？有的，那就是樹狀數(shù)組，他的修改和查詢時間復雜度都是 O(logn) ，綜合來看還是不錯的。如下圖所示，他就是一個樹狀數(shù)組，其中數(shù)組 a[] 是原始數(shù)組，數(shù)組 c[] 是樹狀數(shù)組。

我們令樹狀數(shù)組每個位置存的是子節(jié)點值的和，則有：

通過上面的公式可以發(fā)現(xiàn)一個規(guī)律就是：

比如 c[6] ， 6 的二進制是 (110) ，最右邊有 1 個 0 ，那么 k 就等于 1 ，所以：

在比如 c[4] ， 4 的二進制是 (100) ，最右邊有 2 個連續(xù)的 0 ，那么 k 就等于 2 ，所以：

通過上面的圖我們可以發(fā)現(xiàn)，在樹狀數(shù)組 c[i] 中，如果 i 是奇數(shù)， c[i] 就在第 0 層，也就是樹狀數(shù)組的葉子節(jié)點，并且 ?c[i] = a[i] 。如果 i 不是奇數(shù)，那么在 i 的二進制位中，他右邊有幾個 0 ， c[i] 就在第幾層。我們定義函數(shù) int lowBit(int x) 表示只保留 x 的二進制中最右邊的 1 ，其他位置全部變?yōu)?0 ，比如：

函數(shù) int lowBit(int x) 的代碼如下：

這個很好理解，比如數(shù)字 12 和 -12 ，他們的二進制如下，只要他們進行 & 運算就是我們想要的結果。

令 s[i] 表示元素數(shù)組 a 的前 i 項和，通過上面的圖可以找出 s 和 c 的關系如下：

通過上面等式的關系我們可以得出：

這里的 k1，k2，k3，……，kn 都是 2 的 k 次方，實際上就是不斷的抹去 i 的二進制中右邊的 1 ，直到 i 變成 0 為止。比如數(shù)字 7 ，他的二進制是 111 ，所以 s[111]=c[111]+c[110]+c[100]（這里的數(shù)字是二進制表示），也就是 s[7]=c[7]+c[6]+c[4] 。

這個就是求和，如果要計算數(shù)組 ?a 區(qū)間 [left,right] 的和，可以像下面這樣調(diào)用。

樹狀數(shù)組的求和我們知道了，那么修改呢（這里先討論單點修改）？如果樹狀數(shù)組的一個節(jié)點值被修改了，那么他的父節(jié)點值都要改變，如下圖所示，當 a[5] 的值修改后， c5 ，c6 以及 c8 都要修改。

如果要更改 c[i] 的值，只需要找到 c[i] 的父節(jié)點以及他父節(jié)點的父節(jié)點，……，一直往上走，直到根節(jié)點，全部修改即可。通過圖 1-8 我們可以發(fā)現(xiàn)， c[i] 的父節(jié)點就是 c[i+lowBit(i)] ，所以我們需要以 c[i] 為起點，通過循環(huán)不斷的往上找父節(jié)點然后修改，來看下樹狀數(shù)組的完整代碼：

區(qū)間更新，單點查詢

對于數(shù)組更新和查找可以分為下面幾類：

• 單點更新，單點查詢

• 單點更新，區(qū)間查詢

• 區(qū)間更新，單點查詢

• 區(qū)間更新，區(qū)間查詢

對于“單點更新，單點查詢”，原始數(shù)組就可以做，不需要構建樹狀數(shù)組。而“單點更新，區(qū)間查詢”我們上面剛介紹過，這里來看下“區(qū)間更新，單點查詢”。如果想要區(qū)間更新需要構建差分數(shù)組，在前面 差分數(shù)組 中我們講過，如果要更新原始數(shù)組區(qū)間的值，只需要更新差分數(shù)組兩邊的值即可。其中差分數(shù)組的前綴和就是數(shù)組 a 中某個元素的值，來看下代碼：

區(qū)間更新，區(qū)間查詢

區(qū)間更新可以使用差分數(shù)組，那么區(qū)間查詢呢？假設求數(shù)組 a 的前 n 項和，我們來看下公式推導，如下圖所示。

a 是原數(shù)組， d 是差分數(shù)組，這里我們需要構建兩個樹狀數(shù)組，其中 d1[i] = d[i]，d2[i] = d[i]*(i-1); 。

區(qū)間更新和區(qū)間查詢除了使用樹狀數(shù)組還可以使用線段樹，線段樹不光能區(qū)間求和，還可以求區(qū)間最大值，區(qū)間最小值，功能要比樹狀數(shù)組更強大。

原文鏈接：https://wansuanfa.com/index.php/2023/05/23/%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84/

學習更多數(shù)據(jù)結構，可以在我的文集管理中查看。