# BIT
## infro
又稱樹狀數組，是一種以二進位為基礎的資料結構
功能和線段數差不多
但時間複雜度的常數小，使用的記憶體也較小，實作難度也低

## 先備知識 lowbit
lowbit就是取二進位中，位元為1的最小位元的值(其實就是最右邊的1)
EX:$6\implies 0110 \implies lowbit = 2$
求法是$x \& -x$
$(0110)₂ → (1001)₂+1 → (1010)₂ → (0110)₂\&(1010)₂=2$

$x = 12 = (1100)₂ → lowbit = 4$
$x = 8 = (1000)₂ → lowbit = 8$
## 結構
我們可以從圖看到每個節點的父節點都是自己本身加上自己的lowbit
且每個節點都會把他所有子孫的節點存起來
其實就是每個節點$i$都存著陣列$(i - lowvit(i), i]的值$

## 實作
### lowbit

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

### build
更新就是跑過所有節點
假設跑到i節點就將會存到i節點的所有祖先都把節點i加起來

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

### query
這裡查詢的是前綴和
所以不只回傳bit[i]
還要這個bit沒有存到且在i前面的值，所以要在用遞迴或迴圈的方法找$x - lowbit(x)$的值

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

int query(int x){
    int res = 0;
    while(x > 0){
        res += bit[x];
        x -= lowbit(x);
    }
    return res;
}

### update
和build差不多只是只要操作一個節點

void update(int x, int val) {
    if (x > maxn) return;
    bit[x] += val;
    update(x + lowbit(x), val);
}


void update(int x, int val){
    while(x <= maxn) bit[x] += val, x += lowbit(x);
}

### 區間查詢 & 單點修改

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

int lowbit(int x) {return x & -x;}
void build(){
	for(int x = 1; x <= n; x++) {
		int k = x;
		while(k <= N) bit[k] += arr[x], k += lowbit(k);
	}
}
int query(int x){
	while(x) return query(x - lowbit(x)) + bit[x]; 
	return 0;
}
void update(int x, int val){
    while(x <= N) bit[x] += val, x += lowbit(x);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    build();
    int T, op, l, r, idx, x;
    cin >> T;
    while(T--){
        cin >> op;
        if(op){
            cin >> l >> r;
            cout << query(r) - query(l - 1) << '\n';
        }
        else{ 
            cin >> idx >> x;
            update(idx, x);
        }
    }
    return 0;
}

### 單點查詢 & 區間修改
使陣列arr[i]存兩項的差值，也就是arr[i] -= arr[i - 1]
這樣只要修改邊界兩邊的值就可以做到區間修改
但查詢就會變成只能單點查詢，且query出來的值不再有前綴和的特性

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

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

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