펜윅 트리(Fenwick Tree)란?

펜윅 트리란?

• 펜윅 트리는 배열의 부분 합(prefix sum)을 계산할 때 사용되는 자료구조이다.
• 바이너리 인덱스 트리(Binary Indexed Tree, BIT) 또한 펜윅 트리를 지칭하는 용어이다.

 

펜윅 트리를 왜 써야 하는가?

• 앞에서 펜윅 트리가 부분 합을 계산할 때 사용된다고 했다.
• 정확히 말하자면 펜윅트리는 실시간으로 배열의 요소가 업데이트 되는 상황에서 부분합을 구할 때 사용된다.
• 예를 들어 [4, 5, 6, 7, 8, 9] 배열이 있고, 0번 인덱스부터 3번 인덱스까지 더한다면 4+5+6+7 = 22가 된다.
• 여기서 2번 인덱스를 6에서 10으로 변경한다고 하자.
• 그렇다면 앞서 0번 인덱스부터 3번 인덱스까지 더한 부분 합 22는 더 이상 쓸모없게 된다.
• 2번 인덱스가 6에서 10으로 바뀌었으므로, 0번 인덱스부터 3번 인덱스까지 더한 값은 더이상 22가 아닌, 4+5+10+7 = 26이기 때문이다.
• 마찬가지로 0번 인덱스부터 3번 인덱스까지 더한 부분 합뿐만 아니라 다른 부분 합들(예를 들어, 0번부터 5번 인덱스까지 더한 부분 합) 또한 전부 새로 계산해야 한다.
• 따라서 이렇게 배열 요소의 업데이트가 실시간으로 일어나는 상황이라면, 부분 합을 미리 계산해놓는 것이 의미가 없다.
• 이러한 문제 상황을 해결해줄 수 있는 자료 구조가 바로 펜윅 트리이다.

 

펜윅 트리의 구성

일반적인 자료 구조와 같이 펜윅 트리를 속성(property)과 기능(operation)으로 나누어보겠다.

 

1. 펜윅 트리의 속성

 

• 펜윅 트리는 내부적으로 하나의 배열을 가지고 있다.
• 이 배열은 배열의 각 인덱스를 이진수로 나타내었을 때 그 인덱스의 가장 마지막 1에 해당되는 수만큼의 부분 합을 담고 있다.
• 예를 들어, 26을 이진수로 나타낸 11010에서 가장 마지막 1은 밑줄 친 부분이다.
• 이는 오른쪽에서 두 번째 bit이므로 십진수로 2를 의미한다.
• 따라서 펜윅 트리가 가지고 있는 배열의 26번 인덱스에는 길이가 2인 부분 합을 저장하고 있는 것이다.
• 길이가 2이므로, 이는 실제 배열의 25번부터 26번 인덱스까지 숫자들의 합을 의미한다. (펜윅 트리의 인덱스가 아니다!)
• 다른 예를 들어보자.
• 8을 이진수로 나타내면 1000이 된다.
• 여기서 가장 마지막 1은 밑줄 친 부분이고, 십진수로 8을 의미한다.
• 따라서 펜윅 트리가 가지고 있는 배열의 8번 인덱스에는 길이가 8인 부분 합을 저장하고 있다.
• 이는 실제 배열의 1번부터 8번 인덱스까지 숫자들의 합을 의미한다.

2. 펜윅 트리의 기능

 

• 펜윅 트리의 기능은 update()와 query()로 나뉜다.
• update()는 실제 배열 요소 값의 변경이 일어났을 때, 펜윅 트리의 배열에도 업데이트를 시켜주는 함수이다.
• 구체적으로 update()는 어떤 인덱스를 얼마만큼 증가시킬 때 사용되는 함수이므로 2개의 argument를 넘겨준다.
• 예를 들어, 실제 배열의 26번 인덱스를 3만큼 증가시키고자 하면 update(26, 3)을 호출한다.
• 실제 배열에서 26번 인덱스를 3만큼 증가시키는 작업은 매우 간단하지만, 펜윅 트리의 배열은 부분 합의 배열이므로 실제 배열의 인덱스에 영향을 받게 되는 인덱스가 26번뿐만 아니라 더 많이 존재한다.
• 26번 인덱스를 다시 한번 이진수로 나타내게 되면 11010인데, 실제 배열의 26번 인덱스가 바뀌었을 때 이에 영향을 받는 인덱스들은 가장 오른쪽 1을 반복적으로 더해주면 얻을 수 있다.
• 11010 + 10 = 11100(28)
• 11100 + 100 = 100000(32)
• 100000 + 100000 = 1000000(64)
• ......
• 펜윅 트리 26번 인덱스(가장 오른쪽 1 = 2), 실제 배열의 25-26번 인덱스 부분 합
• 펜윅 트리 28번 인덱스(가장 오른쪽 1 = 4), 실제 배열의 25-28번 인덱스 부분 합
• 펜윅 트리 32번 인덱스(가장 오른쪽 1 = 32), 실제 배열의 1-32번 인덱스 부분 합
• 펜윅 트리 64번 인덱스(가장 오른쪽 1 = 64), 실제 배열의 1-64번 인덱스 부분 합
• 26, 28, 32, 64번 각각의 펜윅 트리 인덱스가 담당하는 실제 배열의 부분 합 인덱스 구간을 보면, 공통적으로 26번 인덱스를 포함하고 있다는 사실을 알 수 있다.

 

• query() 함수는 실제 배열의 1번 인덱스부터 n번 인덱스까지 부분합을 리턴하는 함수이다.
• 이는 펜윅 트리 배열 인덱스 각각이 부분 합을 나타낸다는 특징을 이용해 쉽게 구할 수 있다.
• 26번 인덱스를 이진수로 나타내면 11010이다.
• update() 함수와 반대로, 펜윅 트리 배열 인덱스의 가장 마지막 1을 반복적으로 제거한 인덱스에 해당하는 펜윅 트리 배열 값들을 더하면 부분 합을 구할 수 있다.
• 11010 - 10 = 11000(24)
• 11000 - 1000 = 10000(16)
• 10000 - 10000 = 0(0)
• 펜윅 트리 26번 인덱스(가장 오른쪽 1 = 2), 실제 배열의 25-26번 인덱스 부분 합
• 펜윅 트리 24번 인덱스(가장 오른쪽 1 = 8), 실제 배열의 17-24번 인덱스 부분 합
• 펜윅 트리 16번 인덱스(가장 오른쪽 1 = 16), 실제 배열의 1-16번 인덱스 부분 합
• 따라서 위의 세 가지 값을 더해주면 실제 배열의 1-26번 인덱스 부분 합을 얻을 수 있다.

 

펜윅 트리의 구현

• 펜윅 트리는 세그먼트 트리(Segment Tree)와 용도가 비슷한 자료구조이다.
• 펜윅 트리는 세그먼트 트리에 비해 훨씬 코드가 짧아 구현하기가 쉽고, 대부분의 상황에서 더 좋은 성능을 낸다.
• 심지어 Lazy Propagation로 최적화한 세그먼트 트리보다도 펜윅 트리가 더 나은 경우가 많다.
• 아래는 펜윅 트리의 속성(배열)과 기능(update, query)을 실제로 구현한 코드이다.

 

struct Fenwick
{
    vector<int> fw;
 
    void reset(int n) {
        fw.assign(n+1, 0);
    }
 
    void update(int idx, int val) {
        for (; idx < (int)fw.size(); idx += (idx & -idx)) fw[idx] += val;
    }
 
    //finds [1, r] sum
    int query(int r) { 
        int sum = 0;
        for (; r; r -= (r&(-r))) sum += fw[r];
        return sum;
    }
 
    //finds [l, r] sum
    int query(int l, int r) {
        if(l == 0) return query(r);
        return query(r) - query(l-1);
    }
};

 

 

참고한 자료

• https://en.wikipedia.org/wiki/Fenwick_tree
• https://www.acmicpc.net/blog/view/21