樹狀數組解決數組單點更新後快速查詢區間和的問題

作者：Grey

原文位址：樹狀數組解決數組單點更新後快速查詢區間和的問題

數組在不變的情況下，字首和數組可以用來加速生成<code>i ~ j</code>位置的累加和資訊, 假設字首和數組為<code>preSum</code>，那麼<code>i...j</code>的累加和

<code>sum[i...j] = preSum[j] - preSum[i-1]</code>

但是如果數組要單點修改，則以上的情況不适用，樹狀數組(index tree)就是解決這個問題，時間複雜度可以達到O(logN)。

注：本文所有涉及到的數組操作均從下标1開始計算，下标0位置棄而不用

申請一個輔助數組<code>help</code>, 大小和原始數組<code>arr</code>一樣，儲存原始數組的累加資訊，但是要基于如下規則來儲存。

周遊的位置i如果是奇數，則隻管自己這個位置的内容，即：<code>arr[i] = help[i]</code>。

周遊的位置i如果是偶數，則按如下規律：

<code>0010</code>管<code>0001 ~ 0010</code>的累加和，

<code>00100</code> 管 <code>00001 ~ 00100</code>的累加和，

<code>0110</code> 管 <code>0101 ~ 0110</code>的累加和

...

即某個偶數位置接管的區間是：把這個偶數位置二進制最右邊的1抹掉後再加1得出的位置一直到這個位置本身。

比如：

<code>1010111000</code>這個位置，把最右邊的1抹掉後，值為<code>1010110000</code>,再加1，值為<code>1010110001</code>,是以<code>1010111000</code>這個位置接管的累加和是從<code>1010110001 ~ 1010111000</code>。

通過以上做法生成<code>help</code>數組後，我們可以通過這個<code>help</code>數組快速響應單點更新，并快速求得字首和。

按如上流程生成<code>help</code>數組後，如果要計算<code>1..i</code>位置的累加和，則有如下規則：

第一步，提取出i最右側的1，假設為x，将<code>help[i] + help[i-x]</code>，得出a1

第二步，繼續提取i-x最右側的1，假設為y，将<code>a + help[i- x - y]</code>，得出a2

直到i提取完所有最右側的1，求累加，得到的結果即為<code>1...i</code>上的累加和。

其中<code>index&amp;-index</code>即為index最右側的1。

如果單點有更新，比如需要在index位置上的值增加一個d，此時需要考慮哪些位置受到了牽連。

<code>單點的二進制最末尾的1加1，依次到數組結尾，都是受到牽連的位置</code>

<code>index += index &amp; -index;</code> 即為受到牽連的位置，是以這些位置都要執行加d的操作。

線段樹是樹狀數組的更新版，樹狀數組隻能做到單點更新後，維持累加和資訊的快速更新，線段樹可以支援範圍更新，但是樹狀數組可以很友善改成二維或者三維的，對于線段樹來說，改成二維的太複雜。

二維樹狀數組主要解決：在單點變化時候，快速更新從左上角位置<code>（1,1）</code>累加到<code>(i,j)</code>位置的累加和資訊這個問題。

熟悉一維數組後，二維的樹狀數組比較簡單，原先一維數組隻需要考慮<code>1...i</code>位置累加和，現在二維除了考慮<code>1...i</code>位置累加和，還要考慮<code>1...j</code>位置的累加和

二維樹狀數組的<code>sum</code>方法和<code>update</code>方法如下

即在一維的條件下，增加了一個循環。

現在有了二維樹狀數組，如果要求整個二維平面中，任意<code>[row1,col1]</code>位置到<code>[row2,col2]</code>位置組成的矩形累加和資訊，則可以很友善通過二維數狀數組計算出來：

segment-tree

binary-indexed-tree

算法和資料結構筆記

程式員代碼面試指南（第2版）

算法和資料結構體系班-左程雲