# __*Binary Index Tree (BIT) 學習講義*__
### 引入
如果我們想要利用 *prefix sum* ($p(N)=\displaystyle\sum_{i=1}^{N-1}p(i)$)求得區間極值、區間和等問題，需要 $O(N)$ 的預處理，就可以 $O(1)$ 的查詢，但是如果今天要修改數字，則必須要再用 $O(N)$ 的時間再做一次處理，因為更動後的數字將會全部失效，那...有更快的方法嗎？
### 介紹
當然有！~~不然今天寫這講義做啥~~，*Binary Index Tree*(二元索引樹)利用數字二進位的特性，做出可修改的==動態前綴和==，不論查詢、單點修改都只需要 $O(logN)$ 的時間
### 重要操作
* ___建構、單點修改___
* ___區間查詢___
* ___求答案___
---
(以下程式碼以區間總和為例)

### 建構、單點修改

void update(int num , int val){
    while(num <= N){//N 代表數組長度
        bit[num] += val ;
        num += (num & -num) ;
    }
}

___解釋：___ ___BIT___ 建構的方法就是不斷的做單點更新，每次單點更新都需要 $O(logN)$ 所以更新 $N$ 次就是 $O(NlogN)$

___接下來用一張圖說明他的原理___


___首先可以看到：___
二進位表示法 __xxx1__ 的數字都是存自己區間的答案， __xx10__ 的數字都是存自己跟上一個數字的區間答案，不是每個數字都有儲存，因此 ==___BIT___ 只能解決具有組合性的問題==

___再來可以看到：___
每格處存的區間長度就是該數字二進位的最低位數 ___(lowbit)___
>舉例

:::info
$5$ 的二進位表示法為 __00101__ $(5_{10}=00101_{2})$
$6$ 的二進位表示法為 __00110__ $(6_{10}=00110_{2})$
$8$ 的二進位表示法為 __01000__ $(8_{10}=01000_{2})$
$16$ 的二進位表示法為 __10000__ $(16_{10}=10000_{2})$
:::
___看到什麼？___
:arrow_right: 該數字所影響的區間為自己不斷加上 ___lowbit___ ，直到數字超過範圍

___要怎麼取得 lowbit？___
因為每個數字加上 $-$ 都是原來的==補數(從右數過來到第 $1$ 個 $1$ 相同，之後全部相反)== ，利用 __&__ 可以用 $O(1)$ 取得該數的 ___lowbit___

### 區間和

int sum(int num){
    int ret = 0 ;
    while(num > 0){
        ret += bit[num] ;
        num -= (num & -num) ;
    }
    return ret ;
}

___解釋：___ 迴圈最多次跑 $log_2N$ 次，時間複雜度為 $O(logN)$

___上面有提到：每一格子代表的區間長度為他的 lowbit___

所以前綴和會用到的數字就是==所要求的數字不斷扣到 $0$==

___舉例___
查詢 $1$ ~ $7$ 的和
:::info
$7_{10}=111_2$ ___(所代表區間：$7$ ~ $7$)，區間長度為 $001_2=1$___
$6_{10}=110_2$ ___(所代表區間：$5$ ~ $6$)，區間長度為 $010_2=2$___
$4_{10}=100_2$ ___(所代表區間：$1$ ~ $4$)，區間長度為 $100_2=4$___

___因此：要查詢 $1$ ~ $7$ 的和需要第 $4$、$6$、$7$格的資訊___
:::

### 求答案

___但...如果題目要求 $4$ ~ $7$ 的答案呢？___
簡單，用 ==($1$ ~ $7$ 的答案) $-$ ($1$ ~ $3$ 的答案)==

int query(int l , int r){
    return sum(r) - sum(l - 1) ;
}

___解釋：___ 求兩次區間和，為 $2log_2N$，時間複雜度為 $O(logN)$

### 完整實現 ___BIT___ 程式碼

#include<bits/stdc++.h>
using namespace std ;
#define speed_up ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
const int maxn = 1e5 + 5 ;
int bit[maxn] , N ; 

void update(int num , int val){
    while(num <= N){// N 代表數組長度
        bit[num] += val ;
        num += (num & -num) ;
    }
}

int sum(int num){
    int ret = 0 ;
    while(num > 0){
        ret += bit[num] ;
        num -= (num & -num) ;
    }
    return ret ;
}

int query(int l , int r){
    return sum(r) - sum(l - 1) ;
}

signed main(){
    speed_up ;
    cin >> N ;
    for(int i = 1 , a ; i <= N ; i++){
        cin >> a ;
        update(i , a) ; // build BIT
    }
    cout<<query(3 , 5)<<'\n' ; // 詢問 3 ~ 5 區間和
}

### 比較Segement Tree 跟 Binary Index Tree

| | Segement Tree | Binary Index Tree |
| :--------: | :--------: | :--------: |
| 求區間和 | :heavy_check_mark: | :heavy_check_mark: |
| 求區間極值 | :heavy_check_mark: | :x: |
| 單點修改 | :heavy_check_mark: | :heavy_check_mark: |
| 區間修改 | :heavy_check_mark: | :x: |
>[註] 其實有辦法用 $2$ 棵 ___Binary Index Tree___ 做出區間極值

### 總結

___雖然 Binary Index Tree 感覺能做的事比較少，但是它有==運算速度更快、空間更小(線段樹需要開 $2$ 倍空間)、程式碼更簡單==等優點，綜觀來看，依然是個很優秀的資料結構，提供前綴和計算、修改等操作___

---
### 參考資料
1. [二元索引樹講義](https://hackmd.io/@ruby0322/H1bl6AzY5)
2. [wiwiho的競程講義](https://hackmd.io/@wiwiho/CPN-binary-indexed-tree)

##### `學習講義solo learn`