펜윅트리

펜윅 트리

Fenwick Tree, Binary Indexed Tree(BIT) 라고도 한다.

구간 트리는 구간 합을 빠르게 구하는 데 주로 사용된다. 구간 트리의 진화형태가 펜윅 트리다.

펜윅 트리의 아이디어

"구간 합 대신, 부분 합만을 빠르게 구하는 자료구조를 만들어 두면 구간 합을 계산할 수 있다"

구간 합(range sum) : [3, 6] 과 같은 연속된 구간 합

부분 합(partial sum) : [0, 3] , [0, 8] 과 같이 0번 부터 i까지 합

부분 합 psum의 표현 psum[pos] = A[0] + A[1] + A[2] + ... + A[pos] 로 표현할 수 있다.

구간 [3, 6] 에 대한 합은 psum[6] - psum[2] 로 계산할 수 있다.

구간 [i, j] 에 대한 합은 psum[j] - psum[i-1] 로 계산할 수 있다.

구간 트리와 펜윅 트리의 비교

부분 합(0부터 i까지의 합)만 구한다면, 구간 트리가 미리 계산해 저장하는 상당 수는 필요가 없다.

그림 (a) 는 구간트리, (b)는 펜윅 트리이다.

즉, 하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때 두 구간 중 오른쪽 구간은 항상 지워도 된다.

펜윅 트리는 이 대응을 이용해 1차원 배열 하나에 각 구간의 합을 저장한다.

공간복잡도 O(n)

tree[i] = 그림 (b)에서 오른쪽 끝 위치가 A[i]인 구간의 합

구간 합 을 어떻게 계산할까?

A[pos] 까지의 구간합 psum[pos]를 계산하고 싶으면 그림 (b)에서 pos에서 끝나는 구간의 합 tree[pos]를 답에 더한다.

즉, 그림 (b)에서 색칠한 구간 tree[12], tree[11], tree[7]들은 psum[12]를 계산하기 위해 더해야 하는 구간들이다.

• 어떤 부분 합을 구하든 O(logN) 개의 구간 합만 있으면 된다

pos에서 끝나는 구간 다음으로 더해야 할 구간을 어떻게 찾을까?

• 이제 문제는 pos에서 끝나는 구간 다음으로 더해야 할 구간을 어떻게 찾을까 하는 것입니다.
• 펜윅 트리는 각 숫자의 이진수 표현을 이용해 이 문제를 해결합니다.
• 우선 이진수 표현을 위해 배열 A[]와 tree[]의 첫 원소의 인덱스를 1로 바꾼다.
• 모든 원소의 인덱스에 1을 더해 주는 것이다.

각 구간의 길이는 이진수 표현에서 오른쪽 끝에 있는 0의 개수가 하나 늘 때마다 두 배로 늘어난다.

• psum[7]을 구하기 위해 더해야 하는 숫자는
  • 7에서 끝나는 구간의 합 tree[7] 111
  • 6에서 끝나는 구간의 합 tree[6] 110
  • 4에서 끝나는 구간의 합 tree[4] 100
• 오른쪽 끝 위치의 이진수 표현에서 마지막 비트를 지우면 다음 구간을 쉽게 찾을 수 있음

펜윅 트리 초기화

펜윅 트리를 처음 생성하면 모든 부분 합이 0으로 초기화되므로, 모든 원소가 0인 배열을 표현하게 된다.

• ex) A[5]를 3 늘리고 싶다. 이때 늘려 줘야 할 값들은
  • tree[5] 101
  • tree[6] 110
  • tree[8] 1000
  • tree[16] 10000
• 다른 경우들도 하나하나 시도해 보면 맨 오른쪽에 있는 1인 비트를 스스로에게 더해 주는 연산을 반복하면 해당 위치를 포함하는 구간들을 모두 만날 수 있음
• 예를 들어 110 에서 가장 오른쪽에 있는 비트는 10 이므로, 이를 스스로에게 더하면 1000을 얻을 수 있음

// 펜윅 트리의 구현. 가상의 배열 A[]의 부분 합을 빠르게 구현할 수 있도록 한다. 
// 초기화시에는 A[]의 원소가 전부 0이라고 생각한다.
struct FenwickTree{
    vector<int> tree;
    FenwickTree(int n) : tree(n+1) {}
    // A[0 .. pos]의 부분 합을 구한다.
    int sum(int pos){
        // 인덱스가 1부터 시작한다고 생각 (비트연산 활용을 위해서)
        ++pos;
        int ret = 0;
        while(pos > 0){
            ret += tree[pos];
            // 다음 구간을 찾기 위해 최종 비트를 지운다
            pos &= (pos-1);
        }
        return ret;
    }
    // A[pos]에 val을 더한다
    void add(int pos, int val){
        ++pos;
        while(pos < tree.size()){
            tree[pos] += val;
            pos += (pos & -pos); // -pos : 음수 표현을 위해 비트별 NOT연산을 하고 1을 더한다
        }
    }
};

---

참고

beakjoon 펜윅트리 포스팅

펜윅트리 vs 구간트리

알고리즘 문제해결전략 (구종만 저)