[Java] 2-Dimentional Fenwick Tree

https://uldada.tistory.com/3

2차원 펜윅트리 이해하기(2-dimentional Fenwick Tree)

해당 칸이 들어가는 tree 칸에 대해 전부 들어가야 하므로

각 x row에 대해 모든 y col 칸의 업데이트가 필요하다.

static void update(int x, int y, int v){
    while (x <= n){
        int temp_y = y;
        while (temp_y <= n){
            tree[x][temp_y] += v;
            temp_y += (temp_y & -temp_y);
        }
        x += (x & -x);
    }
}

static int sum(int x, int y){
    int sum = 0;
    while (x > 0){
        int temp_y = y;
        while (temp_y > 0){
            sum += tree[x][temp_y];
            temp_y -= (temp_y & -temp_y);
        }
        x -= (x & -x);
    }
    return sum;
}

 

합은 다음과 같이 구한다.

pw.println(sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1));