Fenwick Tree( BIT )

펜윅 트리 개요

펜윅트리 갱신

< 기본 펜윅트리 갱신 > 

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

 

< 2D 펜윅트리 갱신 >

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

< 기본 펜윅트리 탐색 >

int search(int pos, int y) {
    while(pos>0) {
        ret += BIT[pos];
        
        pos -= (pos & -pos);
    }
}

 

< 2D 펜윅트리 탐색 >

int search(int x, int y) {
    int pos, ret;
    // 2D Fenwick Tree
    ret = 0;
    while(x>0) {
        pos = y;
        while(pos>0) {
            ret += BIT[x][pos];
            pos -= (pos & -pos);
        }
        x -= (x & -x);
    }
    return ret;
}

 

>> (x1, y1) ~ (x2, y2) 구간의 누적합 = search(x2, y2) - ( search(x2, y1-1) + search(x1-1, y2) - search(x1-1, y1-2) )

 

 

참고 자료

- 펜윅트리의 기본 : www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

 

- 2D 펜윅트리 구현 :  www.quora.com/How-do-I-implement-a-2D-binary-indexed-tree-for-range-update-and-range-query-operations

How do I implement a 2D binary indexed tree for range update and range query operations?