» » Binary Indexed Tree

Binary Indexed Tree

   2:33 AM       

#define i64 long long
i64 BIT[mx];
int n;
//1-D BIT
i64 read(int idx){
    i64 sum = 0;
    while (idx > 0){
        sum += BIT[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

void update(int idx, i64 val){
    while (idx <= m){
        BIT[idx] += val;
        idx += (idx & -idx);
    }
}

//2-D BIT
void update(int x , int y , i64 val){
    int y1;
    while (x <= n){
        y1 = y;
        while (y1 <= n){
            BIT[x][y1] += val;
            y1 += (y1 & -y1); 
        }
        x += (x & -x); 
    }
}

i64 read(int x, int y){
    int y1;
    i64 sum = 0;
    while (x > 0){
        y1 = y;
        while (y1 > 0){
            sum += BIT[x][y1];
            y1 -= (y1 & -y1); 
        }
        x -= (x & -x);
    }
    return sum;
}
Tutorial in Topcoder