펜윅 트리(Fenwick Tree)

 

 

Overview

 

펜윅 트리 (Fenwick Tree)는 구간 합을 빠르게 구하기 위해 고안된 자료구조입니다. 결론부터 말씀을 드리면 구간트리의 진화된 형태라고도 할 수 있습니다. 기존의 배열 자체에서 구간 합을 구하기 위해서는 해당 구간을 모두 순회하면서 값을 더해야 하므로 구간 길이에 비례하는 시간이 소요됩니다. O(N)의 시간복잡도를 갖는다는 의미이죠. 이를 더 빠르게 구현하기 위해 고안된 자료구조가 바로 구간트리이며, 구간트리가 갖는 장점을 살리면서 메모리를 훨씬 더 절약할 수 있도록 고안된 자료구조가 바로 펜윅 트리입니다. (구간 트리에 관한 자세한 내용은 구간 트리를 다룬 포스팅을 참고해주세요)

 

Definition

 

펜윅 트리가 갖는 중요한 아이디어는 구간 합을 구하기 위해서 부분 합만을 빠르게 계산할 수 있으면 된다는 것입니다. 아래 그림은 펜윅 트리가 부분 합을 어떻게 저장하는지를 나타냅니다. 총 16개의 값을 저장하는데, 구간 트리와는 다르게 (9~16), (3~4)등의 구간들을 따로 저장하고 있지 않은 것을 확인할 수 있습니다. 바로 이것이 펜윅트리가 구간 합을 구간 트리만큼 빠르게 구하면서 메모리를 4배 가량 절약할 수 있는 이유입니다. (9~16)의 구간은 (1~16)의 구간과 (1~8)의 구간의 차로 구할 수 있기 때문에 해당 구간을 메모리에 저장할 필요가 없게 되는 것입니다. 

 

 

구하고자 하는 구간이 있을 때, 해당 구간의 마지막 값으로 끝나는 구간을 찾은 뒤, 남은 부분을 트리의 왼쪽에서 찾아서 더해주면 되기 때문에 구간 합을 구하는데에 O(lgN)의 시간이 소요된다는 것을 알 수 있습니다. 예를 들면 (1~13)의 구간을 구하기 위해서는 (13) + (9~12) + (1~8)로 구할 수 있는 것입니다. 

 

 

이제 문제는 (13)구간을 찾은 뒤에 어떻게 바로 (9~12)가 가리키는 구간으로 넘어갈 수 있는가입니다. 펜윅트리는 이를 비트연산(Bit Operation)을 통해서 해결합니다. 아래 그림의 Index가 다른 자료구조와는 다르게 0이 아니라 1부터 시작하는 이유도 이와 관련이 있습니다. 

 

https://www.crocus.co.kr/666

 

 

Bit Operation

 

다음 그림은 펜윅 트리를 설명한 논문에서 각 구간에 대해 오른쪽 끝 원소의 인덱스와 이진수 표현 사이의 관계를 나타냅니다. 각 구간의 길이는 오른쪽 끝에 있는 0의 개수가 하나 늘어날 때마다 2배씩 늘어나며, 펜윅트리는 이를 이용해서 더해야 하는 다음 구간의 길이를 계산합니다.

 

 

예를 들어, (1~11)의 구간합을 구하는 경우를 생각해보겠습니다. 

1. 먼저 제일 오른쪽에 있는 원소가 11이므로 11을 찾습니다. 11의 이진수 표현은 01011입니다. 

2. 다음으로 더해야 하는 구간은 (9~10)이므로 10을 찾아야 합니다. 10의 이진수 표현은 01010이므로 11의 제일 마지막 1을 0으로 바꾸어주면 된다는 것을 확인할 수 있습니다. 

3. 마찬가지로 (1~8)의 구간을 더하면 됩니다. 8의 이진수 표현은 01000이므로 10의 제일 마지막 1을 0으로 바꾸어주면 된다는 것을 확인할 수 있습니다. 

 

 

정리해보면 

01011 -> 01010 -> 01000 순으로 0을 하나씩 지워나가면 되는 것을 확인할 수 있습니다. 즉, 펜윅트리는 비트 연산을 이용해서 구간트리의 장점을 살려 O(lgN)의 시간만에 부분 합을 이용한 구간 합을 빠르게 구할 수 있도록 합니다.

 

 

https://arxiv.org/pdf/1612.09083.pdf

 

Source Code

 

    static class FenwickTree {
        long[] tree;
        int n;
        FenwickTree(int n) {
            this.n = n;
            this.tree = new long[n+1];
        }

        // calculate sum
        public long sum(int pos) {
            long sum = 0;
            int temp = pos;
            while(temp > 0) {
                sum += this.tree[temp];
                temp -= (temp & -temp);
            }
            return sum;
        }

        // update value
        public void update(int pos, long val) {
            int temp = pos;
            while(temp <= this.n) {
                this.tree[temp] += val;
                temp += (temp & -temp);
            }
        }
    }