Fenwick Tree (펜윅 트리, Binary Indexed Tree = BIT)

배열에서 어느 구간의 구간합을 구한다고 하자. 누적합을 저장한 배열을 사용하면 특정 구간의 구간합을 단순히 두 위치의 값을 빼줌으로 상수 시간에 쉽게 구할 수 있다. 그러나 만약 배열의 값이 자주 바뀐다면 문제가 생긴다. 만약 원래 배열의 k번째 값이 변경된다면 누적합을 저장한 배열에서 k번째와 그 이후의 값들은 모두 변경해주어야 한다. 최악의 경우엔 누적 값을 저장한 배열의 n개의 값들을 다 변경해주어야 한다. 데이터의 양이 많으면서 데이터의 값이 자주 수정된다면 누적합은 사용하기 적합하지 않은 방법이다. 이때 펜윅트리를 사용하면, O(logn)에 해결할 수 있다. 이번 글에서는 펜윅트리에 대해 알아보겠다. 참고로 이번 글에서  n번째라고 하면 배열에서 처럼 0부터 셈을 하는 것이 아닌 일상에서 처럼 1부터 셈을 했을 때를 나타낸다. 이는 펜윅트리의 구현과 관계가 있다.

 

펜윅 트리(Fenwick)의 구조

펜윅트리 구조

펜윅트리의 구조를 들여다보자. 배열의 값들은 어떤 구간 내의 값들의 합을 나타낸다. 위 표에서 12번째 항목은 원래 배열의 9~12번째 값들의 합을 나타낸다. 13번째 항목은 원본 배열에서의 13번째 값만 포함한다. 6번째 항목은 원본의 5~6번째 값들의 합을 나타내고, 16번째 값은 원본 배열의 1부터 16번째까지의 값들의 합이다. 위의 표를 보고 펜윅트리의 n번째 값이 원본 배열의 어느 부분의 값들의 합을 나타내는지 알 수 있다면, 어느 규칙에 의해서 펜윅트리의 k번째 값이 원본 배열의 특정한 값들의 합을 이루는지도 알 수 있는가?

 

펜윅트리는 배열 인덱스의 이진법 표현을 활용한 자료구조이다. 이 때문에 Binary Indexed Tree라고도 불린다. 펜윅트리의 k번째 값은 원본 배열에서 구간 [k - LSBIT(k) + 1, k]의 값들의 합이다. 여기서 LSBIT(k)를 "k를 이진수로 변환하였을 때 비트 값이 1인 비트들 중 최 하위 비트가 나타내는 값"이라고 하자. LSBIT에 대한 몇 가지 예제이다.

• k = 6 일 때 : 6은 2진법으로 0110(2)이다. 이때 LSBIT(k) = 0010(2) = 2이다.
• k = 3 일 때 : 3은 2진법으로 0011(2)이다. 이때 LSBIT(k) = 0001(2) = 1이다.
• k = 8 일 때 : 8은 2진법으로 1000(2)이다. 이때 LSBIT(k) = 1000(2) = 8이다.
• k = 12 일 때 : 12는 2진법으로 1100(2)이다. 이때 LSBIT(k) = 0100(2) = 4이다.

펜윅트리의 k번째 값은 원본 배열의 구간 [k - LSBIT(k) + 1, k]의 값들이라고 하였다. 다시 말하자면 k부터 앞으로 LSBIT(k) 개의 값들의 합이다. 몇 가지 예시를 들어보자.

• k = 6일 때 펜윅트리의 6번째 값은 원본 배열의 구간 [6 - 2 + 1 = 5 ,6]의 합을 나타낸다. (5~6)
• k = 3일 때 펜윅트리의 3번째 값은 원본 배열의 구간 [3 - 1 + 1 = 3 ,3]의 합을 나타낸다. 즉 원본 배열의 3번째 값이다. (3)
• k = 8일 때 펜윅트리의 8번째 값은 원본 배열의 구간 [8 - 8 + 1 = 1 ,8]의 합을 나타낸다. (1~8)
• k = 12일 때 펜윅트리의 6번째 값은 원본 배열의 구간 [12 - 4 + 1 = 9 ,12]의 합을 나타낸다. (9~12)

길이가 16인 배열 arr = {10,9,8,7,6,5,4,3,2,1,0,0,0,0,0,0} 이 있다. arr을 이용하여 펜윅트리 f를 만들었을 때 f의 모습은 다음과 같다.

 

펜윅트리 업데이트

원본 배열의 k번째 값이 변경되었다면 펜윅트리에서는 원본 배열의 k번째 값을 포함하고 있는 모든 값을 수정해주어야 한다. 만약 원본 배열의 3번째 값에 3이 추가된 경우 펜윅트리에서 바꿔주어야 하는 값들은 3,4,8,16 번째 값들이다.

펜윅트리에서 k번째 값을 포함하고 있는 인덱스들을 순회하는 건 어렵지 않은데, 그저 k에 LSBIT를 계속 더해나가면 된다. k=3인 경우에 대해서 자세히 살펴보자.

• k = 3 일 때 : 3 + LSBIT(3) = 4 임으로 k를 4로 갱신한다.
• k = 4 일 때 : 4 + LSBIT(4) = 8 임으로 k를 8로 갱신한다.
• k = 8 일 때 : 8 + LSBIT(8) = 16 임으로 k를 16으로 갱신한다.

LSBIT(x)는 비트 연산으로 간단하게 구할 수 있음으로 구현하는데도 어렵지 않다. 어떤 수 x가 있을 때 LSBIT(x)는 c++로 아래처럼 쓸 수 있다.

x & -x

이를 이용해서 펜윅트리를 업데이트하는 코드를 만들어 보자. 아래 코드는 원본의 idx번째의 값이 diff 만큼 수정되었을 경우 펜윅트리 v를 업데이트하는 코드이다.

void update(vector<int> &v,int diff,int idx){
    const int len = v.size();
    for(int i = idx; i < len; i += i & -i){
        v[i] += diff;
    } 
}

 

 

누적합 구하기

임의의 구간에 대해 구간합을 구하기 전에 1~k번째 값들의 합인 누적합을 구하는 법을 먼저 알아보자. 펜윅트리에서 원본 배열의 1~k번째까지의 합을 구하기 위해 인덱스를 적절히 골라야 한다. 1~k번째의 값들 중 어느 하나도 두 번 이상 포함되지 않으면서 한 번씩은 반드시 포함되게 선택해야 한다.

k = 7일 때 누적합을 구하기 위해 펜윅트리를 사용하는 경우를 보자. 펜윅트리의 7,5,4번째 값들은 각각 원본 배열의 7, 5~6, 1~4번째 값들의 합임으로 이들을 더해주면 된다.

k = 11 인 경우 펜윅트리의 11, 10, 8번째 값들을 더해주면 된다.

 

이 값들도 LSBIT를 사용하여 순회할 수 있는데, 업데이트를 할 때랑은 반대로 k번째 값에 대해 누적합을 구하고 싶다면 k에 LSBIT를 계속 빼주면 된다. k가 11이었을 때를 자세히 살펴보자.

• k = 11 : 11 - LSBIT(11) = 10 임으로 k를 10으로 갱신한다.
• k = 10 : 10 - LSBIT(10) = 8 임으로 k를 10으로 갱신한다.
• k = 8 : 8 - LSBIT(8) = 0이다.

누적합 부분도 c++코드로 작성하기 간단하다.

int sum(vector<int> &v,int idx){
    int ret = 0;
    for(int i = idx; i > 0 ; i -= i & -i){
        ret += v[i];
    }
    return ret;
}

 

구간합 구하기

위에서 누적합을 구했으므로 구간 시작과 끝의 누적합을 빼주면 구간합이 된다. 예를 들어 구간 [min, max]의 구간합을 구하기 위해서는 (min-1까지의 누적합) - (max까지의 누적합)을 계산해주면 된다.

int sum(vector<int> &v,int lidx,int ridx){
    return sum(v,ridx) - sum(v,lidx-1);
}

 

펜윅트리의 단순한 구현

아래는 펜윅트리의 단순한 구현과 실행 결과이다.

#include <iostream>
#include <vector>

using namespace std;

void update(vector<int> &v,int diff,int idx){
    const int len = v.size();
    for(int i = idx; i < len; i += i & -i){
        v[i]+=diff;
    } 
}

int sum(vector<int> &v,int idx){
    int ret = 0;
    for(int i = idx; i > 0 ; i -= i & -i){
        ret += v[i];
    }
    return ret;
}

int sum(vector<int> &v,int lidx,int ridx){
    return sum(v,ridx) - sum(v,lidx-1);
}

void print(vector<int> vec){
    for(int i=1; i<vec.size();++i){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}

int main(void){
    int arr[16] = {10,9,8,7,6,5,4,3,2,1,0,0,0,0,0,0};
    vector<int> f(17);

    for(int i=0;i<10;++i){
        update(f,arr[i],i+1);
    }

    print(f);
    cout<<endl;
 
    update(f,3,3);
    print(f);

    cout<<sum(f,11)<<endl;
    cout<<sum(f,6)<<endl;
    cout<<sum(f,7,11)<<endl;
}

10 19 8 34 6 11 4 52 2 3 0 3 0 0 0 55 

10 19 11 37 6 11 4 55 2 3 0 3 0 0 0 58 
58
48
10

이 구현은 펜윅트리는 단일 값 업데이트와 구간 값 계산이 O(log n)에 가능하다. 그러나 이 구현은 몇 가지 한계가 있다. 여러 개의 값을 같은 diff로 업데이트할 때 반복문과 함께 update 함수를 사용하면 시간 복잡도가 최악의 경우 O(nlog n)이다. 또, 세그먼트 트리와 달리 구간의 최댓값, 최솟값을 찾는 데 사용할 수 없다. 그러나 첫 번째 상황의 경우에는 O(log n)에 처리할 수 있는 다른 구현이 있고, 두 번째 상황의 경우에는 펜윅트리 하나가 아닌 두 개를 사용하여 처리하는 방법이 있다. 언젠가 이 방법들에 대해서 공부해보자.