[Algorithm] Fenwik Tree(Binary Index Tree)

Fenwik Tree(Binary Index Tree)는 구간합을 구할때 많이 사용되는 자료구조이다.

처음 배울 때 분명히 이해 했는데 매번 다시 볼때마다 새로워서 계속 코드를 보면서 공부해야할것 같다.

 

Fenwik Tree를 구현하려면 어떤 수 N을 이진수로 만들었을 때 마지막 1의 위치를 구할 수 있어야 한다

 

L[i]배열의 값을 직접적으로 사용하지는 않지만 Fenwik Tree를 이해하기 위해서는 이해하고 있어야 할 듯 하다.

따라서 L[i]값을 수식으로 구하면 (i & -i)가 된다. (L[i] = (i & - i))

 

그리고  배열 A[1] ~ A[N]에 N개의 수가 들어있다고 할 때 

Tree[i]에는 A[i - L[i + 1]] ~ A[i]까지의 합이 저장되게 하면 된다.

 

Fenwik Tree를 Udate 함수는 다음과 같다.

#define NMAX 1000000
 
int N;
int tree[NMAX];
void update(int i, int diff){
    for(;i < N; i += i&-i){
        tree[idx] += diff;
}

그리고 구간합을 구하는 Query함수는 아래와 같다.

int query(int i){
    int ret = 0;
    for(; i > 0; i -= i&-i){
        ret += tree[i];
    return ret;
}

이때 특정 인덱스까지의 합을 구하는 함수는 아래처럼 사용이 가능하다.

int sum(int l, int r){
    return sum(r) - sum(l - 1);
}

Update 함수의 경우 한번에 하나의 좌표에 대한 구간합을 수정하게 된다.

이때의 시간 복잡도는 O(log N)이 되는데 만약 문제가 달라져서

한번에 M개의 데이터를 업데이트하는 명령이 반복적으로 들어오게 된다면 

Update 함수를 수행하는 데만 O(M*log N)의 시간복잡도를 가지게 되서 비효율적이게 된다.

 

그래서 Fenwik Tree를 이용해서 구간을 업데이트 할 때는 Update함수를 모든 구간에 대해서 다 부르는 것이 아니라

조금 다른 형식으로 Update 함수를 부르게 된다. 

 

l부터 r까지  diff만큼 업데이트 한다고 할 때 

l에대해서 diff만큼 업데이트 하고 r + 1에 대해서 -diff만큼 업데이트 시켜주면 두번의 Update 함수를 통해 업데이트가 가능해진다.

void range_update(int l, int r, int diff) {
    update(l, diff);
    update(r + 1, -diff);
}

이때 주의 사항은 이때 Query를 통해 반환되는 값이 구간합이 아니라 실제 그 위치의 값이라는 점이다.

처음에 관련된 주제로 문제를 풀 때 당연히 구간합인줄 알고 사용했다가 한참동안 삽질했던 것 같다.