본문 바로가기
카테고리 없음

펜윅 트리(Binary Indexed Tree) 구현 (구간 합을 더 가볍게)

by 코드 아카이브 2026. 2. 21.

앞서 다루었던 '세그먼트 트리(Segment Tree)'는 구간 합, 최댓값, 최솟값 등 다양한 구간 쿼리를 O(log N)의 속도로 처리할 수 있는 만능 자료구조입니다. 하지만 구현을 위해 원본 배열 크기의 4배에 달하는 거대한 메모리 공간이 필요하며, 코드가 다소 길고 복잡하다는 단점이 있습니다. 만약 우리가 풀어야 할 문제가 '단순한 구간 합(Range Sum)'과 '단일 인덱스의 값 업데이트(Point Update)' 단 두 가지만을 요구한다면 굳이 무거운 세그먼트 트리를 쓸 필요가 없습니다. 메모리는 원본 배열과 똑같은 1배(N)만 차지하면서도 코드는 단 몇 줄에 불과하고, 속도마저 비트 연산을 활용해 극단적으로 빠른 천재적인 자료구조가 있습니다. 바로 1994년 피터 펜윅(Peter Fenwick)이 고안한 '펜윅 트리(Fenwick Tree)', 혹은 '이진 인덱스 트리(Binary Indexed Tree, BIT)'입니다. 오늘 이 글에서는 펜윅 트리를 움직이는 비트마스킹의 마법을 낱낱이 파헤쳐 보겠습니다.

1. 펜윅 트리의 탄생: 세그먼트 트리의 다이어트

세그먼트 트리는 왼쪽 자식과 오른쪽 자식의 정보를 모두 간직합니다. 하지만 피터 펜윅은 "구간 합을 구할 때, 굳이 모든 노드의 정보를 다 저장할 필요가 있을까? 특정 숫자의 이진수 표현(비트)을 잘 활용하면, 배열의 일부 데이터만으로도 전체 합을 거꾸로 유추해 낼 수 있지 않을까?"라는 놀라운 아이디어를 떠올렸습니다.

펜윅 트리는 크기가 N인 1차원 배열 단 하나만으로 트리를 구성합니다. 배열의 각 인덱스는 자신이 책임지는 '구간의 길이'가 정해져 있는데, 이 길이는 전적으로 해당 인덱스를 이진수(Binary)로 표현했을 때의 가장 마지막 1의 위치(LSB, Least Significant Bit)에 의해 결정됩니다.

2. 펜윅 트리의 심장: LSB (가장 마지막 1비트) 추출 기법

펜윅 트리를 이해하기 위한 0순위 선행 지식은 바로 특정 정수의 '가장 마지막에 있는 1비트(LSB)'의 값을 빠르게 추출하는 비트 연산 공식입니다.

2-1. 마법의 비트 연산: K & -K

컴퓨터는 음수를 표현할 때 '2의 보수(모든 비트를 뒤집고 1을 더함)' 방식을 사용합니다. 어떤 양수 정수 K와 그 음수 -K를 비트 AND(&) 연산하면, 아주 놀랍게도 가장 오른쪽에 있는 1비트만 남고 나머지는 모두 0으로 지워지는 마법이 일어납니다.

  • K = 12일 때, 이진수로는 1100(2)입니다.
  • -K = -12일 때, 이진수 2의 보수는 0100(2)입니다. (앞부분의 수많은 1은 생략)
  • 12 & -12를 연산하면 0100(2), 즉 십진수 4가 튀어나옵니다.

이 결과로 나온 숫자 4가 의미하는 것은 무엇일까요? 펜윅 트리에서 12번 인덱스 배열이 '자기 자신을 포함하여 앞으로 4칸 분량의 누적 합'을 저장하고 있다는 뜻입니다. 즉, tree[12]에는 9번, 10번, 11번, 12번 원소의 합이 뭉텅이로 저장되어 있습니다.

3. 펜윅 트리의 핵심 로직: O(log N) 탐색과 갱신

비트 연산을 활용하면 배열을 넘나드는 탐색(Query)과 갱신(Update) 로직이 세그먼트 트리와 비교할 수 없을 정도로 압도적으로 짧아집니다.

3-1. 구간 합 구하기 (Prefix Sum Query)

1번 인덱스부터 K번 인덱스까지의 누적 합을 구하고 싶다면, K번 인덱스부터 시작해서 'LSB 값을 빼가면서(K = K - (K & -K))' 0이 될 때까지 점프하며 배열의 값을 더해주면 됩니다.


// 1부터 index까지의 누적 합을 구하는 함수 (Java)
int sum(int index) {
    int result = 0;
    while (index > 0) {
        result += tree[index];
        index -= (index & -index); // LSB를 빼면서 앞으로 점프!
    }
    return result;
}

예를 들어 13번(1101)까지의 합은 tree[13](13번 1칸) + tree[12](9~12번 4칸) + tree[8](1~8번 8칸)을 차례대로 더하여 딱 3번의 반복만으로 13칸의 구간 합을 완벽하게 구해냅니다.

3-2. 특정 데이터 갱신하기 (Point Update)

원본 배열의 K번째 값이 변경되었다면, 이 값을 포함하고 있는 펜윅 트리 내의 모든 부모 노드들을 갱신해야 합니다. 합을 구할 때와는 반대로, K번 인덱스부터 시작해서 'LSB 값을 더해가면서(K = K + (K & -K))' 배열의 끝에 도달할 때까지 점프하며 차이값(Diff)을 더해줍니다.


// index 위치의 값을 갱신하는 함수
void update(int index, int diff) {
    while (index <= N) {
        tree[index] += diff;
        index += (index & -index); // LSB를 더하면서 뒤로(부모로) 점프!
    }
}

이러한 비트 이동의 마법 덕분에 펜윅 트리는 재귀 함수 호출조차 필요 없는 단순한 while문 하나만으로 O(log N)의 극한의 효율을 자랑하게 됩니다.

[핵심 요약]
1. 펜윅 트리(BIT)는 세그먼트 트리를 다이어트시켜 원본 배열과 동일한 크기의 1차원 배열 1개만으로 구간 합과 업데이트를 O(log N)에 처리하는 효율적인 자료구조입니다.
2. K & -K라는 천재적인 비트 연산을 통해 이진수의 마지막 1비트(LSB)를 추출하고, 이를 더하거나 빼는 방식으로 트리의 부모/자식 노드를 넘나들며 점프합니다.
3. 코드가 극단적으로 짧고 메모리 효율이 뛰어나, 복잡한 범위 쿼리(최댓값/최솟값 등)가 아닌 단순 구간 누적 합을 다루는 코딩 테스트 문제에서 압도적인 위력을 발휘합니다.

티스토리툴바