# BIT
**Binary Index Tree(線上演算法)**

用來計算前綴和

#### 單點修改:
不斷往大的找=>因為每一個點都會被上面的包覆

void update(int MAXN,int h,int add){
    while(h<=MAXN){
        tree[h]+=add;
        h=h+(h&-h);
    }
}

#### 前綴查詢:
不斷往小的找=>計算前綴和
#注意:h要>0不然會無限循環,換句話說,BIT的索引值要從1開始

int query(int h){
    int sum=0;
    while(h>0){
        sum+=tree[h];
        h=h-(h&-h);
    }
    return sum;
}

### 二維bit

在D維bit的每一個節點都還存有一顆D維的bit,可用來求
1. 小於x且小於y的前綴和query(x-1,y-1)
2. 小於等於x且小於y的前綴和query(x,y-1)
3. 小於x且小於等於y的前綴和query(x-1,y)
4. 小於等於x且小於等於y的前綴和query(x,y)

#### 單點修改

void update(int x,int y){
    while(x < MAXN){
        int ty=y;
        while(ty < MAXN){
            bit[x][ty]++;
            ty+=ty & -ty;
        }
        x+=x & -x;
    }
}

#### 前綴查詢

int query(int x,int y){
    int sum=0;
    while(x){
        int ty=y;
        while(ty){
            sum+=bit[x][ty];
            ty-=ty & -ty;
        }
        x-=x & -x;
    }
    return sum;
}