# binary indexed tree

* 計算前綴和，有前綴和也就可以算區間和
* **1-indexed**
> 如果要用 BIT 做最大值，數字只能被改大，做最小值，數字只能被改小
* 用差分$O(\log n)$區間操作

更新：

void update(int pos, int x){
    while(pos<=n){
        bit[pos]+=x;
        pos+=pos & (-pos);
    }
}

查詢：

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a;
    cin>>n;
    rep(i,1,n+1){
        cin>>a;
        update(i, a);
    }
    cout << query(n) << NL;
    }

區間加值
---

LL b1[500010]={0}, b2[500010]={0};//b1:prefix D, b2:prefix D*i
LL n, q, a, x, y, k;

void upd(LL *bit, LL pos, LL x){
    while(pos<=n){
        bit[pos]+=x;
        pos+=pos & (-pos);
    }
}

void range(LL l, LL r, LL x){
	upd(b1, l, x);
	upd(b1, r+1, -x);
	upd(b2, l, l*x);
	upd(b2, r+1, -(r+1)*x);
}

LL query(LL *bit, LL pos){
    LL res=0;
    while(pos>0){
        res+=bit[pos];
        pos-=pos & (-pos);
    }
    return res;
}

LL pre_sum(LL pos){
	return (pos+1)*query(b1, pos)-query(b2, pos);
}

二維bit
---
https://tioj.ck.tp.edu.tw/problems/1869

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

LL bit[1050][1050]={0};
int n;

void update(int x, int y, LL v){
    x++, y++;
    while(x<=n){
        int tmp=y;
        while(tmp<=n){
            bit[x][tmp]+=v;
            tmp+=tmp & (-tmp);
        }
        x+=x & (-x);
    }
}

LL get(int x, int y){
    x++, y++;
    LL res=0;
    while(x>0){
        int tmp=y;
        while(tmp>0){
            res+=bit[x][tmp];
            tmp-=tmp & (-tmp);
        }
        x-=x & (-x);
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>n;
    while(cin>>t){
        if(t==0) break;
        if(t==1){
            int a, b, z;
            cin>>a>>b>>z;
            update(a, b, z);
        }
        else{
            int x1, y1, x2, y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<get(x2, y2)-get(x1-1, y2)-get(x2, y1-1)+get(x1-1, y1-1)<<NL;
        }
    }
}