# 樹狀樹組-BIT
> [color=blue]快速求取區間和的助手
## 回顧
還記得前綴和嗎，他也是用來求區間和的，但你應該會發現，若當中有一個值需要被修改，那整列都會被動到。
以下是一個比較表，了解BIT強大之處
| 資料結構 | 查尋區間和 | 單點修改值 |
| ------- | ----------- | ----------- |
| 純陣列 | $O(n)$ | $O(1)$ |
| 前綴和 | $O(1)$ | $O(n)$ |
| BIT | $O(log(n))$ | $O(log(n))$ |
## 用途 & 概念
BIT用於在快速求取區間和的同時，又能保證快速修改。感覺像是陣列與前綴和的優點結合下的產物，不過其複雜程度也是三者之中最高的。以下為示意圖，其中數字代表它儲存的區間。
```graphviz
digraph BIT{
nodesep=1 // increases the separation between nodes
node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Blue, style=dashed] //All the lines look like this
"1~8"->{"1~4" "5~6" "7"}
"1~4"->{"1~2" "3"}
"1~2"->{"1"}
"5~6"->{"5"}
{rank=same;"1~2" "5~6"} // Put them on the same level
{rank=same;"1" "3" "5" "7"}
}
```
如果想要知道`1~5`的和，可以查詢`1~4+5`。以下為查詢所需區間表。
| 1 | 1~2 | 1~3 | 1~4 | 1~5 | 1~6 | 1~7 | 1~8 |
|:---:|:---:|:-------:|:---:|:-------:|:---------:|:-------------:|:---:|
| 1 | 1~2 | 1~2 & 3 | 1~4 | 1~4 & 5 | 1~4 & 5~6 | 1~4 & 5~6 & 7 | 1~8 |
可以發現，在元素數量為8時，最多會需要查詢3個區間就可以得到`1~n`的值，接著就像前綴和那樣，用`1~R - 1~(L-1)`就可以求出所有區間的和了。
## 實作
BIT一般都是用陣列實作，用區間最大值作為存放位置(例如`1~4`放在`4`)。那搜尋與修改呢？這部分就比較複雜了，需要了解一些二進位制，如果你已經理解二進位制了，那就繼續往下看吧。
### 二進位表
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| 000001 | 000010 | 000011 | 000100 | 000101 | 000110 | 000111 | 001000 |
### lowbit
lowbit是在二進位下右邊看過來最前面的1，例如：6(000110)就是2(000010)，一樣提供一個表
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|:------:| ------ |:------:|:------:|:------:|:------:|:------:|:------:|
| 000001 | 000010 | 000011 | 000100 | 000101 | 000110 | 000111 | 001000 |
| 000001 | 000010 | 000001 | 000100 | 000001 | 000010 | 000001 | 001000 |
### 查詢
可以發現，$x$重複$-lowbit(x)$會變成0，且途中會經過所有需要的區間。以7為例
```graphviz
digraph BIT{
nodesep=1// increases the separation between nodes
node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Blue, style=dashed] //All the lines look like this
"7(000111) : 7 "->"6(000110) : 5~6 "
"6(000110) : 5~6 "->"4(000100) : 1~4 "
"4(000100) : 1~4 "->"0(000000) : none"
//{rank=same;"7(000111) : 7 " "6(000110) : 5~6 " "4(000100) : 1~4 " "0(000000) : none"}
}
```
只要將所有經過的區間加在一起，就可以得到區間和了。這也呼應為何他查尋的複雜度為$O(log(n))$，因為$n$只會有$log(n)$個$bit$。
### 修改
修改也有些相似，變成$x$加上$lowbit(x)$，就會將上面有包含到他的區間也都更新到。以三為例
```graphviz
digraph BIT{
nodesep=1// increases the separation between nodes
node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Blue, style=dashed] //All the lines look like this
"3(000011) : 3 "->"4(000100) : 1~4 "
"4(000100) : 1~4 "->"8(001000) : 1~8 "
}
```
這樣最多也是$O(log(n))$。也可以發現$lowbit$的重要性。
### 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
// 與 int lowbit(x){ return x&-x;}
// 用define或函式雖然不會讓你的程式碼寫起來比較快，但可以使其較易於理解。
using ll=long long;
ll bt[200010];
ll a[200010];
// build 函式是透過逐個更新陣列的所有元素來建構BIT
void build(int n){
for(int i=1;i<=n;++i)
for(int x=i;x<200005;x+=lowbit(x))
bt[x]+=a[i];
}
// 單點加值
void add(int x,int k){
a[x]+=k;
for(int i=x;i<=200005;i+=lowbit(i))
bt[i]+=k;
}
// 由單點加值衍生出來的單點修改
void modify(int x,int k){
add(x,k-a[i]);
}
// 搜尋1~x的區間和
ll find_sum(int x){
ll ret=0;
for(int i=x;i>0;i-=lowbit(i))
ret+=bt[i];
return ret;
}
// 用計算(1~r) - (1~(l-1))算出所有區間的區間和
ll query(int l,int r){
return find_sum(r)-find_sum(l-1);
}
```
## 習題
### Q-13-1 [區域調查(POJ.1195 Mobile phones 改編)](https://zerojudge.tw/ShowProblem?problemid=d796)
#### 題目敘述 :
給一個矩陣 T(1,1), T(1,2),.... T(N,M)，求 T(x1,y1) 到 T(x2,y2) 的總和 或者是修改 T(x1,y1) 的值
#### 輸入說明 :
每組輸入的第一行會有兩個正整數 N Q ( 1 ≦ N ≦ 250, Q ≦ 50,0000)
接下來會有 N 行，每行上會有 N 個元素 M ( 0 ≦ M ≦ 32767 )
接下來會有 Q 行，倘若第一個數字為 1，則接下來會有四個數字
x1 , y1 , x2 , y2， 1 ≦ x1 , y1 , x2 , y2 ≦ 250
請輸出元素 $S={( x , y ) | x1 ≦ x ≦ x2, y1 ≦ y ≦ y2 }$符合的所有元素總和
倘若第一個數字為2，則接下來會有三個數字
x1 , y1 , V， 1 ≦ x1 , y1 ≦ 250 , 0 ≦ V ≦ 32767,
請修改 ( x1 , y1 )= V ; 此行不必輸出
#### 輸出說明 :
若為調查，則輸出區域中的元素總和，若為修改，則不必輸出
#### 範例輸入 1 :
```
5 10
3 2 2 3 7
4 4 0 3 8
2 4 7 2 3
5 9 6 1 4
7 1 7 1 1
2 2 2 1
1 5 4 5 5
2 2 1 7
1 3 2 1 5
1 2 5 4 5
1 1 2 2 1
2 2 2 7
2 4 5 5
1 3 3 4 5
1 4 3 2 2
```
#### 範例輸出 1 :
```
2
42
15
13
24
33
```
---
### Q-13-2 [2D rank finding problem(98學年度中投區資訊學科能力競賽)](https://zerojudge.tw/ShowProblem?problemid=d847)
#### 題目敘述 :
二度空間上的排名計算問題(2D rank finding problem)：給定二度平面空間(2D)上的點A = (a1,a2)與點B = (b1,b2)，其大小關係定義為若A > B 若且唯若 a1> b1 且 a2 > b2 ;亦即A點在B點的右上方。如下圖中，B >A, C>A, D>A, D>C, D> B。值得注意的是，並非任意兩點均可以決定大小關係，如下圖中的點A與點E，點D與點E等，無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x1,y1), (x2,y2), …, (xn,yn)，定義某一個點的排名(rank) 為所給的點集合中，比該點小的點的個數。
設計一個程式，從檔案讀取點的名稱與座標，計算出在所給定的集合中，所有點的排名值。
#### 輸入說明 :
有多組測試資料
每組的第一行有一個數字N ( 1 ≦ N ≦ 10000 )
接下來會有N行，每行上會有兩個數字 x y ( 1 ≦ x , y ≦ 1000 )
#### 輸出說明 :
請按照輸入的順序，求出對於 ( x , y ) 有多少個點 ( a , b )
在它的左下方 a < x , b < y
#### 範例輸入 1 :
```
5
961 404
640 145
983 888
539 71
437 532
```
#### 範例輸出 1 :
```
2
1
4
0
0
```
---
### Q-13-3 [低地距離(2020年10月APCS)](https://zerojudge.tw/ShowProblem?problemid=f315)
#### 題目敘述 :
輸入一個長度為 2n 的陣列，其中 1 ~ n 的每個數字都剛好各 2 次。
i 的低窪值的定義是兩個數值為 i 的位置中間，有幾個小於 i 的的數字。
以 $[3, 1, 2, 1, 3, 2]$ 為例，1的低窪值為 0, 2 的低窪值值為 1, 3 的低窪值為 3。
請對於每個 1 ~ n 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。
#### 輸入說明 :
第一行有一個正整數 n
第二行有 2n 個正整數，以空格分隔，保證 1 ~ n 每個數字都恰好出現兩次。
1≤n≤100000
#### 輸出說明 :
輸出 1 ~ n 每個數字的低窪值總和。
#### 範例輸入 1 :
```
3
3 1 2 1 3 2
```
#### 範例輸出 1 :
```
4
```
> **2022/1/10**
> [name=mtmatt] [time=Mon, Jan 10, 2022 21:10 ] [color=#00eeff]
Sign in with Wallet
Connect another wallet