## Prefix Sum
前綴和。可用來解決「區間和」的問題。
### 考慮以下問題：
> 存在一個序列 $A$，對於此序列詢問 index $l$ 到 index $r$ 的總和。
> Example: A = [1, 2, 5, 3, 6]
> 詢問 index 2 及 index 4 的總和
> 應回傳 A[2] + A[3] + A[4] = 5 + 3 + 6 = 14
最簡單的方法就是每次處理時，都從 index $l$ 遍歷到 index $r$，但這麼做的時間複雜度會隨著詢問次數上升。
透過觀察不難發現，對於任意詢問 [$l$, $r$]，都能視作 [$0$, $r$] 減去 [$0$, $l - 1$]。
- **舉個例子：**
$A$ = [1, 5, 6, 2, 5, 9]
詢問 [$2$, $5$]
$=$ 6 + 2 + 5 + 9
$=$ (1 + 5 + 6 + 2 + 5 + 9) - (1 + 5)
$=$ [$0$, $5$] - [$0$, $2 - 1$]
$=$ [$0$, $5$] - [$0$, $1$]
### 資料結構
參考以上想法，可以發現單純儲存「 index $0$ 到任意 index 的總和」就能應付所有詢問。而這就是 Prefix Sum 所儲存的東西。
假設 $A$ 有 $n$ 個值，現在先考慮儲存 index $0$ 到 index $i$ 的總和，可以發現所儲存的值會等於 index $0$ 加到 index $(i - 1)$ 的值**再加上** index $i$ 的值。以此類推，我們可以發現儲存的值會等於當前值加上原陣列的值，因此構建 Prefix Sum 時只需遍歷 $A$ 一遍就行。
由於需要儲存的資料為 index $0$ 到 $i$ 的和，而 $i$ 小於等於 $n$ ，因此至少需要 $n$ 個空間，再加上一開始的和是 $0$，總共需要 $n + 1$ 的空間（這邊也可以是 $n - 1$ 個空間，看需不需要儲存一開始的 $0$ 及最後的 $sum(A)$）
範例程式碼如下
```cpp=
int A[] = [1, 5, 6, 2, 5, 9];
vector<int> preSum(A.size() + 1, 0); // n+1 的空間，預設值為 0
for(int i = 0; i < A.size(); i++){
preSum[i + 1] = preSum[i] + A[i]; //現在的值會等於前一個值加上 A 現在的值
//因為 A 的索引最小是 0 ，而如果要符合上面
//的算式，那麼 Prefix Sum 就必須用 1-index
}
```
若要搜尋 [$l$, $r$]
```cpp=
int ans = preSum[r] - preSum[l];
```
### 參考題目
[303. Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/description/)
## Binary Index Tree (BIT)
二元索引樹，又稱**樹狀數組**。可用來解決「動態區間和」的問題。
### 考慮以下問題：
> 存在一個序列 $A$，所有元素皆有預設值 $0$；對於此序列會有以下動作：
> 1. 把 $A_i$ 加上指定值 $v$
> 2. 詢問 [$0$, $r$] 區間和。
如果在每次修改都去更新 Prefix Sum 的元素的話，時間複雜度跟一開始講到的一樣會隨著詢問次數上升。
而 BIT 與 preSum 類似，都儲存了某個區段的區間和，但與 preSum 不同的是，在一次修改後的更新， preSum 需要 $O(n)$ 的複雜度，而 BIT 只需要 $O(log\ n)$
### 資料結構
以 $B$ 來表示 BIT 這個資料結構，在實作中可以直接使用 array 作為 BIT 。由於使用 `1-index` ， $B[0]$ 不會被使用到，因此它的空間與 prefix Sum 一樣是 $n + 1$。
<font style="background-color: GreenYellow">$B$ 的每個 index $i$ 都代表了往下數 $lowbit(i)$ 個數的區間和。</font>其中 $lowbit(i)$ 指的是 $i$ 轉成二進位後，把最低位的 $1$ 以外的 $1$ 都變成 $0$ 所代表的值。以 $(4)_{10}$ , $(14)_{10}$ , 及$(15)_{10}$ 為例子：
- $(4)_{10}$：
- 計算 $lowbit(4)$
$(4)_{10} = (100)_2$
$lowbit(4) = (100)_2 = 4_{10}$
- 得出 index $4$ 的值是往下數 $lowbit(4)$ 也就是 **4 個值**的總和。
index $4$ 的值是 index $(100)_2$ + index $(011)_2$ + index $(010)_2$ + index $(001)_2$
以範圍表達就是 $[1, 4]$
- $(14)_{10}$：
- 計算 $lowbit(14)$
$(14)_{10} = (1110)_2$
$lowbit(14) = (0010)_2 = 2_{10}$
- 得出 index $14$ 的值是往下數 $lowbit(14)$ 也就是 **2 個值**的總和。
index $14$ 的值是 index $(1110)_2$ + index $(1101)_2$
以範圍表達就是 $[13, 14]$
- $(15)_{10}$：
- 計算 $lowbit(15)$
$(15)_{10} = (1111)_2$
$lowbit(15) = (0001)_2 = 1_{10}$
- 得出 index $15$ 的值是往下數 $lowbit(15)$ 也就是 **1 個值**的總和。
index $15$ 的值是 index $(1111)_2$
以範圍表達就是 $[15, 15]$
<font style="background-color: Orange">$B$ 的 index $i$ 代表了 [$i - lowbit(i) + 1$, $i$] 的區間和</font>，像是 index $14$ 的值是[$14 - 2 + 1$, $14$] ，也就是 [$13$, $14$]。而 index $4$ 或 index $15$ 的值可以根據上面的方法算出來。
再觀察<font style="background-color: GreenYellow">上面提到的特性</font>，index $i$ 所包含的範圍只會在下一個 lowbit() 嚴格大於 lowbit(i) 的 index 包含到。以剛剛的 $(4)_{10}$ , $(14)_{10}$ , 及$(15)_{10}$ 為例子：
- $(4)_{10}$：
以範圍表達就是 $[1, 4]$
繼續找範圍被覆蓋到的 index：
- $(5)_{10} = (4)_{10} + (1)_{10}$：
- 範圍是 $[5, 5]$
- $(6)_{10} = (4)_{10} + (2)_{10}$：
- 範圍是 $[5, 6]$
- $(7)_{10} = (4)_{10} + (3)_{10}$：
- 範圍是 $[7, 7]$
- $(8)_{10} = (4)_{10} + (4)_{10}$：
- **範圍是 $[1, 8]$
找到了**
- $(14)_{10}$：
以範圍表達就是 $[13, 14]$
繼續找範圍被覆蓋到的 index：
- $(15)_{10} = (14)_{10} + (1)_{10}$：
- 範圍是 $[15, 15]$
- $(16)_{10} = (14)_{10} + (2)_{10}$：
- **範圍是 $[1, 16]$
找到了**
- $(15)_{10}$：
以範圍表達就是 $[15, 15]$
繼續找範圍被覆蓋到的 index：
- $(16)_{10} = (15)_{10} + (1)_{10}$：
- **範圍是 $[1, 16]$
找到了**
可以發現<font style="background-color:yellow;">**每個 $i$ 的範圍會被 $i + lowbit(i)$ 所包含**</font>，因此在更新 $i$ 時，也要同時更新 $i + lowbit(i)$。而同時因為 $0$ 並不往下包含任何數字，因此 $BIT$ 整體是以 $1$-index 來做處理。
而對於 $lowbit(i)$ ，則可以用以下算式來處理：
$$
lowbit(i) = i\ \&\ -i
$$
因為負數會反相加一的緣故，所以可以保留最低位元的 $1$ ，這剛好就是我們要求的 $lowbit(i)$。
對於範例問題，應該要有 `update(index, target)` 及 `query(index)`，而由於 BIT 可以處理動態區間和的問題，在初始化時通常是初始化一個全為 0 的空陣列，再根據題目的 $A$ 一個一個加上去更新每個需要更新的值。
#### update
`update` 需更新會用到此範圍所有 bit 的節點，依照<font style="background-color:yellow;">上述特性</font>，假設需要更新的值為 $B[index]$，那麼 $B[index + lowbit(index)]$ 的值也要更新，以此類推。
##### 時間複雜度 $O(log\ n)$
因為 lowbit 為最小位的 1 ，每遞迴一次就會進位(二進制) ， 所以遞迴次數最多為 $log\ n$
#### query
`query` 所求為 $[1, index]$ 的總和，<font style="background-color: orange">由於 index 所包含的部分不一定會覆蓋到 index $1$ </font>，我們可以先求出 index 所覆蓋的部分，再求出 $[1, index - lowbit(index)]$ 所覆蓋的部分。因此，$[1, index]$ 的總和可以拆分為
$$
[1, index - lowbit(index)] + [index - lowbit(index) + 1, index]
$$
而 $[index - lowbit(index) + 1, index]$ 就是 $BIT[index]$ 所表達的值，因此整個算式能夠改寫成
$$
[1, index - lowbit(index)] + BIT[index]
$$
而前面的 $[1, index - lowbit(index)]$ 也可以透過這個算式遞迴算出[1, index]的總和。
##### 時間複雜度 $O(log\ n)$
因為 lowbit 為最小位的 1 ，每遞迴一次就會扣掉最小位的 1 ， 所以遞迴次數最多為 $log\ n$
範例程式碼：
```cpp=
int lowbit(int value){
return value & (-value);
}
void update(int index, int target){
while (index < B.size()){
B[index] += target;
index += lowbit(index);
}
}
int query(int index){
int sum = 0;
while (index > 0){
sum += B[index];
index -= lowbit(index);
}
return ans;
}
```
### 參考題目
[307. Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/description/)
Sign in with Wallet
Connect another wallet