일반적인 숫자 배열(flat array)과 비교했을 때, 펜윅 트리(Fenwick Tree)는 요소 업데이트와 접두사 합(prefix sum) 계산이라는 두 연산 사이에서 훨씬 더 나은 균형을 제공합니다.
m개의 숫자를 담고 있는 평면 배열의 경우, 요소 자체를 저장하거나 접두사 합을 저장하는 두 가지 방식 중 하나를 선택해야 합니다. 전자의 경우 접두사 합을 계산하는 데 선형 시간(O(m))이 소요되고, 후자의 경우 배열 요소를 수정·업데이트하는 데 선형 시간이 걸립니다. 물론 두 경우 모두 나머지 하나의 연산은 상수 시간에 수행할 수 있습니다.
반면 펜윅 트리는 두 연산을 모두 O(log m) 시간 안에 처리할 수 있도록 해줍니다. 이는 숫자들을 트리 형태로 표현하고, 각 노드의 값을 해당 서브트리(subtree)에 속한 숫자들의 합으로 취급함으로써 얻어집니다. 이러한 트리 구조 덕분에 모든 연산을 O(log m)번의 노드 접근만으로 완료할 수 있습니다.
펜윅 트리의 기본 구조
펜윅 트리는 1부터 시작하는 인덱스(one-based array)를 사용한다고 생각하면 가장 쉽게 이해할 수 있습니다.
- 인덱스 j가 2의 거듭제곱인 요소는 처음 j개 요소의 합을 저장합니다.
- 인덱스가 서로 다른 두 개의 2의 거듭제곱의 합으로 표현되는 요소는, 바로 앞선 2의 거듭제곱 위치 이후부터의 요소들의 합을 저장합니다.
기본적으로 각 요소는 트리상에서 자신의 부모(parent) 노드 이후의 값들의 합을 담고 있으며, 그 부모는 인덱스에서 최하위 비트(least-significant bit, LSB)를 0으로 지우면 찾을 수 있습니다.
접두사 합 계산 방법
임의의 위치(인덱스)까지의 합을 구하려면, 해당 인덱스의 이진수 표현(binary expansion)을 살펴보고, 이진수에서 1인 각 비트에 대응하는 요소들을 더하면 됩니다.
예를 들어, 첫 11개 값의 합을 구하고 싶다고 가정해 봅시다. 11은 이진수로 1011입니다. 이 숫자에는 1비트가 세 개 있으므로, 세 개의 요소를 더해야 합니다: 1000, 1010, 1011. 이들은 각각 1~8번째, 9~10번째, 11번째 값들의 합을 나타냅니다.
C 언어 구현 예제
다음은 간단한 C 구현 코드입니다.
#define LSB(i) ((i) & -(i)) // 최하위 비트만 남기고 나머지 비트를 모두 0으로 만든다
int A1[SIZE];
int sum(int i) // 인덱스 1부터 i까지의 합을 반환
{
int sum = 0;
while (i > 0)
sum += A1[i], i -= LSB(i);
return sum;
}
void add(int i, int k) // 인덱스 i인 요소에 k를 더한다
{
while (i < SIZE)
A1[i] += k, i += LSB(i);
}