---
tags: 進階班
---

# 樹狀數組 Binary Index Tree (BIT)

## 用途

在要使用線段樹的狀況下，某些題目可以用寫起來較快的 BIT 實作，提升速度。

除此之外，BIT 記憶體較小，在某些線段樹空間會爆的情況下可使用

## 結構

先畫個示意圖：


從這個圖可以很直觀的看出：**用 BIT 做 `query`，可以把 `arr[1] ~ arr[n]` 很輕鬆的求出來。**

\
而它其實是：對於每個節點 $n$，它存著陣列 $(n - lowbit(n),\; n]$ 的值。

**lowbit 是甚麼？**

對於每個數，其 lowbit 值為「數字轉為二進位後，位元為 $1$ 的最小位元所代表之值」

舉例：$3_{(10)}\rightarrow 011_{(2),}\;lowbit = 1,\quad 6_{(10)}\rightarrow 011 0_{(2)},\;lowbit = 2$

所以 `bit` 的 `query(1, n)` 時間複雜度是多少呢？

:::spoiler `隨便帶個數字想想看`
\
是 $O(lgN)$ 喔，跟線段樹一樣。

設 $x = 2^a + 2^b + 2^c + \;...\;\;(a > b > c > \;...)$

則 `query(x) = ... + bit[2^a + 2^b + 2^c] + bit[2^a + 2^b] + bit[2^a]`
:::

## 操作

1. **區間查詢 & 單點修改**
2. **單點查詢 & 區間修改**

如果你要 單點查詢 & 單點修改，請用一般陣列就好
如果你要 區間查詢 & 區間修改，請用線段樹 + 懶標記

## 實作

### 通則

先宣告 `BIT, arr`，再訂下陣列大小 `maxn`

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5;
LL bit[maxn + 1], arr[maxn + 1];

$lowbit$ 其實可以用函數獲得：

int lowbit(int x) {return x & -x;}

可以自己證明看看 :poop:

要做 `build()` 時

void build(){
	for(int x = 1; x <= n; x++) {
		int k = x;
		while(k <= maxn) bit[k] += arr[x], k += lowbit(k);
	}
}

觀察上方的 bit 示意圖可得知，對於一個 `arr[x]`，若 `bit[k]` 存著 `arr[x]`，則 `k = 離 x 最近的 2 的倍數、4 的倍數、8 的倍數...`

前提是 `k >= x`。

而 2 的倍數、4 的倍數、8 的倍數... 它們最低的 $lowbit$ 是 2, 4, 8...

那麼上方的 `build()` 就出來了！

要做 `query(n)` 時

LL query(int x){
	while(x) {
		return query(x - lowbit(x)) + bit[x]; 
	}
	return 0LL; //if(x == 0)
}

可以回上面翻「想想看」

### 細節
1. 區間查詢 & 單點修改

不須做任何特殊處理，直接實作

    void update(int i, LL x){ // 相當於 arr[i] += x
        while(i <= maxn) bit[i] += x, i += lowbit(i);
    }
    int main(){
        int n;
        cin >> n;
        for(int x = 1; x <= n; x++) cin >> arr[x];
        build();
        int ques, op, l, r, i, x;
        cin >> ques;
        while(ques--){
            cin >> op;
            if(op) cin >> l >> r, cout << query(r) - query(l - 1) << '\n';
            else cin >> i >> x, update(i, x);
        }
        return 0;
    }

2. 單點查詢 & 區間修改

`arr[i] -= arr[i - 1]`，存相鄰兩項差值

這樣區間和時，僅 `arr[l]` 及 `arr[r + 1]` 有改變。

    void update(int l, int r, LL x){
        while(l <= maxn) bit[l] += x, l += lowbit(l); //update bit[l] - bit[l - 1]
        while(r <= maxn) bit[r] -= x, r += lowbit(r); //update bit[r + 1] - bit[r]
    }
    int main(){
        int n;
        cin >> n;
        for(int x = 1; x <= n; x++) cin >> arr[x];
        for(int x = n; x; x--) arr[x] -= arr[x - 1];
        build();
        int ques, op, l, r, i, x;
        cin >> ques;
        while(ques--){
            cin >> op;
            if(op) cin >> i, cout << query(i) << '\n';
            else cin >> l >> r >> x, update(l, r + 1, x);
        }
        return 0;
    }

## 相關題目

[a477: March's New Textbook](http://203.64.191.163/ShowProblem?problemid=a477)

## 小結

基本上，BIT 的題目都可以拿線段樹來解，只是有可能：

1. 空間爆掉
2. 寫起來較為冗長，比較有可能出現 bug

但多知道一個解法，總比時間緊迫時來不及刻線段樹好

那麼，有甚麼線段樹題是 BIT 解不了的呢？

由於 BIT 只能 $query(1, \;n)$，只要做不到 $query(l, \;r) = query(1, \;r)$ 和 $query(1,\; l - 1)$ 逆運算的題目都不行。

e.g. 區間最大、最小值