# Binary Index Tree

以下介紹 [RMQ on BIT](http://ioinformatics.org/oi/pdf/v9_2015_39_44.pdf) ( 以 minimum 為例 )

維護區間總和請自己類推 ( 基本上只需要一棵 LBT )

## 基本結構

### Left Binomial Tree ( LBT )

$B_k$ 樹高 k 有 $2^k$ 個節點
他是遞迴定義的
$B_0$ 是最小單位 ( 一個點 )
$B_k$ 是由 **把一個 $B_{k-1}$ 當作另一個 $B_{k-1}$ 的最左小孩接起來** 組成

節點 $i$ 的父親是 $i + 2^{LSB(i)}$
節點 $i$ 維護區間 $[i - 2^{LSB(i)} + 1, i]$


### Right Binomial Tree ( RBT )

跟 LBT 相似，左改右即可

節點 $i$ 的父親是 $i - 2^{LSB(i)}$
節點 $i$ 維護區間 $[i, i + 2^{LSB(i)} - 1]$


## Query

時間複雜度: $O(logN)$

假設要查詢的是 $[5, 13]$

1. 從 5 開始在 LBT 往上走訪 $\leq 13$ 的節點 ( $5 \to 6 \to 8$ )
2. 從 13 開始在 RBT 往上走訪 $\geq 5$ 的節點 ( $13 \to 12 \to 8$ )

就是以下這些區間取 min 的意思

5:  [5,5]
6:  [6,7]
8:  8
13: [13,13]
12: [9,12]

## Update

時間複雜度: $O(logN)$ or $O(log^2N)$

在 RBT 要更新 $A[p]$ 為 $v$ ( A 是原始陣列 )
從 $p$ 往上走訪，更新所有包含 $p$ 的節點 ( 區間 )

假設要更新的區間是 $[x, y]$ ( $y = x + 2^{LSB} - 1$ 且 $x \leq i \leq y$ )
這個區間的最小值在 $A[q]$

1. $if \ p \ne q$，$min(A[p],A[q])$
2. $if \ p = q$，$min(query(x,p-1),A[p],query(p+1,y))$

所有不一樣 $x$ 的 $query(x,p-1)$ 可以一起做完
所有不一樣 $y$ 的 $query(p+1,y)$ 可以一起做完

LBT 的更新同理可知