2026-02-03 | 7 min read | 104 | 자료구조 펜윅 트리 알고리즘

2-11. 자료구조: Fenwick Tree (Binary Indexed Tree)

1. 펜윅 트리 (Fenwick Tree) 소개

펜윅 트리 (Fenwick Tree)는 1994년 컴퓨터 과학자 Peter Fenwick에 의해 고안된 자료구조로, 흔히 "Binary Indexed Tree (BIT)"라고도 불립니다. 펜윅 트리는 배열의 각 prefix sum을 효율적으로 계산하고, 배열의 특정 인덱스 값을 업데이트하는 데 특화되어 있습니다. 기존의 배열을 사용하는 방식보다 훨씬 적은 시간 복잡도로 이러한 연산을 수행할 수 있다는 장점이 있습니다. 특히, 동적 데이터를 다루는 상황, 즉, 데이터의 잦은 변경과 쿼리가 함께 발생하는 상황에서 펜윅 트리는 뛰어난 성능을 발휘합니다.

1) 왜 펜윅 트리가 필요할까?

일반적인 배열에서 prefix sum을 계산하는 것은 간단합니다. 인덱스 i까지의 합을 구하려면 배열의 처음부터 i번째 요소까지 모두 더하면 됩니다. 그러나 배열의 특정 값을 변경하는 update 연산이 발생하면, 변경된 값 이후의 prefix sum들을 모두 다시 계산해야 합니다. 이는 O(N)의 시간 복잡도를 가지게 됩니다.

예를 들어, 배열 [1, 2, 3, 4, 5]가 있고, 3번째 요소(인덱스 2)의 값을 0으로 변경한다고 가정해 봅시다. 이 경우, prefix sum을 다시 계산해야 합니다. 즉, prefix sum[2]부터 prefix sum[4]까지 모두 다시 계산해야 합니다.

펜윅 트리는 이러한 문제를 해결하기 위해 고안되었습니다. 펜윅 트리를 사용하면 prefix sum을 계산하는 데 O(log N) 시간, 특정 요소의 값을 변경하는 데 O(log N) 시간밖에 걸리지 않습니다.

2) 펜윅 트리의 장점

빠른 prefix sum 계산: O(log N)
빠른 update 연산: O(log N)
메모리 효율성: 기존 배열과 동일한 공간을 사용
구현의 용이성: 세그먼트 트리 (Segment Tree)에 비해 구현이 간단

3) 펜윅 트리의 활용 분야

펜윅 트리는 다음과 같은 문제 해결에 유용하게 사용될 수 있습니다.

구간 합 (Range Sum) 쿼리: 특정 구간의 합을 빠르게 계산해야 하는 경우
빈도수 계산 (Frequency Counting): 데이터의 빈도수를 효율적으로 관리해야 하는 경우
역수열 (Inversion Count): 정렬되지 않은 배열에서 역수열의 개수를 계산해야 하는 경우
동적 데이터 처리: 데이터의 변경과 쿼리가 빈번하게 발생하는 경우

2. 펜윅 트리 (Fenwick Tree)의 핵심 원리

펜윅 트리는 각 노드가 특정 구간의 합을 저장하도록 설계된 이진 트리 구조를 기반으로 합니다. 펜윅 트리의 핵심은 각 노드가 담당하는 구간을 결정하는 방법과, 이를 통해 prefix sum을 효율적으로 계산하고 업데이트하는 방법입니다.

1) 구조 이해

펜윅 트리는 일반적인 이진 트리와는 다르게, 배열의 인덱스를 직접 사용하여 구조를 표현합니다. 각 노드는 원래 배열의 특정 요소들의 합을 저장하며, 이 합을 계산하기 위해 특별한 규칙을 사용합니다. 각 노드가 담당하는 구간은 해당 노드의 인덱스를 이진수로 표현했을 때, 최하위 비트(LSB, Least Significant Bit)를 기준으로 결정됩니다.

예시:

인덱스 1 (001): arr[0]의 값을 저장
인덱스 2 (010): arr[0] + arr[1]의 값을 저장
인덱스 3 (011): arr[2]의 값을 저장
인덱스 4 (100): arr[0] + arr[1] + arr[2] + arr[3]의 값을 저장
인덱스 5 (101): arr[4]의 값을 저장
인덱스 6 (110): arr[4] + arr[5]의 값을 저장
인덱스 7 (111): arr[6]의 값을 저장
인덱스 8 (1000): arr[0] + arr[1] + arr[2] + arr[3] + arr[4] + arr[5] + arr[6] + arr[7]의 값을 저장

이진수 표현에서 최하위 비트는 LSB(index)로 표현될 수 있으며, 이는 index & -index 연산을 통해 계산할 수 있습니다. 예를 들어, LSB(6)은 다음과 같습니다.

6 = 0110 (이진수)
-6 = 1010 (2의 보수)
6 & -6 = 0010 (2)

따라서 인덱스 6의 노드는 arr[4] + arr[5]의 값을 저장합니다.

펜윅 트리 구조 설명 뒤

2) LSB (Least Significant Bit) 이해

LSB는 펜윅 트리의 핵심입니다. LSB를 이해하면, 각 노드가 어떤 데이터를 포함하는지, 그리고 prefix sum을 어떻게 효율적으로 계산할 수 있는지 알 수 있습니다.

LSB 계산: index & -index
LSB의 역할: 노드가 저장하는 구간의 크기 및 위치 결정
- LSB(i)는 인덱스 i가 포함하는 구간의 길이를 나타냅니다.
- 예를 들어, LSB(8)은 8이므로, 인덱스 8의 노드는 arr[0]부터 arr[7]까지의 합을 저장합니다.
- LSB(6)은 2이므로, 인덱스 6의 노드는 arr[4] + arr[5]의 값을 저장합니다.

3) Prefix Sum 계산 (getSum)

prefix sum을 계산하는 방법은 다음과 같습니다.

현재 인덱스 i에서 시작합니다.
현재 인덱스 i에 저장된 값을 prefix sum에 더합니다.
i = i - LSB(i)를 수행하여 부모 노드로 이동합니다.
i가 0보다 클 때까지 2~3단계를 반복합니다.

예를 들어, prefix sum(6)을 계산하는 과정은 다음과 같습니다.

i 6: prefix sum + BIT[6] (arr[4] + arr[5])
i 6 - LSB(6) 6 - 2 4: prefix sum + BIT[4] (arr[0] + arr[1] + arr[2] + arr[3])
i 4 - LSB(4) 4 - 4 = 0: 반복 종료

따라서 prefix sum(6)은 BIT[6] + BIT[4]로 계산됩니다.

4) Update 연산 (update)

특정 인덱스의 값을 업데이트하는 방법은 다음과 같습니다.

현재 인덱스 i에서 시작합니다.
BIT[i]의 값을 변경된 값만큼 더합니다.
i = i + LSB(i)를 수행하여 자식 노드로 이동합니다.
i가 펜윅 트리의 범위를 벗어날 때까지 2~3단계를 반복합니다.

예를 들어, arr[2]의 값을 변경하는 경우, 펜윅 트리에서 해당하는 노드들을 업데이트해야 합니다.

i = 3: BIT[3] 업데이트
i 3 + LSB(3) 3 + 1 = 4: BIT[4] 업데이트
i 4 + LSB(4) 4 + 4 = 8: BIT[8] 업데이트
i가 범위를 벗어나면 종료

3. 펜윅 트리 (Fenwick Tree) 구현

펜윅 트리의 구현은 비교적 간단합니다. 다음은 Python으로 구현된 펜윅 트리의 예시입니다.

class FenwickTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.bit = [0] * (self.n + 1)  # 1-based indexing
        self.original_arr = arr  # Original array for reference

        for i in range(self.n):
            self.update(i, arr[i])

    def lsb(self, i):
        return i & -i

    def get_sum(self, i):
        """Calculate prefix sum up to index i."""
        s = 0
        i += 1  # 1-based indexing
        while i > 0:
            s += self.bit[i]
            i -= self.lsb(i)
        return s

    def update(self, i, val):
        """Update the value at index i."""
        diff = val - self.original_arr[i]
        self.original_arr[i] = val  # Update the original array
        i += 1  # 1-based indexing
        while i <= self.n:
            self.bit[i] += diff
            i += self.lsb(i)

1) 초기화 (`init`)

self.bit: 펜윅 트리를 저장할 배열 (1-based indexing 사용)
self.original_arr: 원래 배열을 저장하여 값 업데이트 용이하게 함
초기 배열을 순회하며 각 값을 펜윅 트리에 update합니다.

2) LSB 계산 (`lsb`)

index & -index 연산을 통해 LSB를 계산합니다.

3) Prefix Sum 계산 (`get_sum`)

1-based indexing을 사용하므로, 입력 인덱스에 1을 더합니다.
while 루프를 통해 조상 노드로 이동하며 값을 더합니다.
i -= self.lsb(i): 부모 노드로 이동

4) Update 연산 (`update`)

원래 배열의 값을 먼저 업데이트합니다.
1-based indexing을 사용하므로, 입력 인덱스에 1을 더합니다.
while 루프를 통해 자식 노드로 이동하며 값을 더합니다.
i += self.lsb(i): 자식 노드로 이동

4. 응용 및 활용 사례

펜윅 트리는 다양한 문제 해결에 활용될 수 있습니다.

1) 구간 합 (Range Sum) 쿼리

구간 [l, r]의 합을 계산하려면, prefix sum(r) - prefix sum(l-1)을 계산합니다.

python def range_sum(self, l, r): """Calculate the sum of elements in the range [l, r].""" return self.get_sum(r) - self.get_sum(l - 1)

2) 빈도수 계산 (Frequency Counting)

각 숫자의 발생 빈도를 계산하고 관리하는 데 사용될 수 있습니다.
배열의 각 요소는 숫자를 나타내고, 펜윅 트리는 각 숫자의 발생 횟수를 저장합니다.

3) 역수열 (Inversion Count)

역수열은 정렬되지 않은 배열에서, arr[i] > arr[j]이고 i < j인 쌍의 개수입니다.
펜윅 트리를 사용하여 역수열 개수를 효율적으로 계산할 수 있습니다.
1. 배열의 각 요소를 순회하며, 해당 요소보다 작은 숫자의 개수를 펜윅 트리에서 구합니다.
2. 해당 숫자를 펜윅 트리에 추가합니다.
3. 각 요소에 대해 계산된 작은 숫자들의 개수를 모두 더하면 역수열의 개수가 됩니다.

5. 주의사항과 트러블슈팅

1) 1-based vs. 0-based Indexing

펜윅 트리는 일반적으로 1-based indexing을 사용합니다.
구현 시, 배열의 인덱스를 1부터 시작하도록 조정해야 합니다.
get_sum과 update 함수에서 인덱스 변환에 주의해야 합니다.

2) 음수 인덱스 처리

lsb 연산은 음수 인덱스에서도 올바르게 동작합니다.
그러나, 1-based indexing을 사용하므로, 0보다 작은 인덱스는 사용하지 않도록 주의해야 합니다.

3) 오버플로우

데이터 타입의 크기에 따라 오버플로우가 발생할 수 있습니다.
int 대신 long long과 같은 더 큰 데이터 타입을 사용하거나, 적절한 모듈로 연산을 적용하여 오버플로우를 방지해야 합니다.

4) 디버깅

펜윅 트리의 동작을 시각화하여 디버깅하는 것이 도움이 될 수 있습니다.
각 update 및 get_sum 연산 후, 펜윅 트리의 상태를 출력하여 올바르게 동작하는지 확인합니다.

6. 결론

펜윅 트리는 배열 기반의 데이터를 효율적으로 관리할 수 있는 강력한 자료구조입니다. prefix sum 계산, 업데이트 연산, 구간 합 쿼리 등 다양한 문제에 적용될 수 있으며, 알고리즘 문제 해결 및 실무에서 널리 활용됩니다. LSB의 개념을 정확하게 이해하고, 1-based indexing에 유의하여 구현하면 펜윅 트리의 장점을 최대한 활용할 수 있습니다.