컴퓨터공학 300 주제 시리즈의 056번째 글이다. 전체 지도는 여기.

한 줄 요약

펜윅 트리(Binary Indexed Tree)는 길이 n 짜리 배열 하나에 “인덱스의 최하위 1비트만큼의 구간 합”을 저장해, 누적 합 질의와 원소 갱신을 모두 O(log n) 에 처리하는 구조로, 세그먼트 트리보다 메모리가 절반이고 코드는 열 줄 남짓이다.

왜 필요한가

앞 글의 세그먼트 트리는 구간 질의와 갱신을 O(log n) 에 해냈다. 그런데 문제가 “합”뿐이라면 더 가벼운 방법이 있다. 1994년 Peter Fenwick 은 데이터 압축의 산술 부호화에서 기호 빈도의 누적 합을 빠르게 갱신·조회하려고 이 구조를 발표했다. 논문 제목도 “누적 빈도표를 위한 새로운 자료구조”다.

펜윅 트리의 매력은 단순함이다. 트리를 노드와 포인터로 만들지 않는다. 배열 하나와 비트 연산 i & -i 하나가 전부다. 그래서 실수할 여지가 적고, 캐시에 잘 맞고, 메모리는 정확히 n 칸이다. 누적 빈도, 순위 계산, 역순 쌍 세기, 2차원 누적 합처럼 “합”으로 표현되는 문제에서는 거의 항상 첫 선택지다.

핵심 개념

최하위 비트(lowbit)

정수 i 의 이진 표현에서 가장 오른쪽 1비트만 남긴 값을 lowbit(i) 라 하자. 2의 보수 표현에서 -i 는 i 의 비트를 뒤집고 1을 더한 것이므로, i & -i 가 정확히 그 비트를 뽑아 낸다.

i      = 12 = 0b1100
-i     =      ...10100   (2의 보수)
i & -i =      0b0100 = 4

파이썬 정수는 크기 제한이 없지만, 문서는 비트 연산이 “무한한 부호 비트를 가진 2의 보수로 수행한 것처럼” 계산된다고 명시한다(Python — Bitwise Operations on Integer Types). 그래서 이 기법이 그대로 동작한다.

각 칸이 맡는 구간

1부터 세는 배열 tree 에서 tree[i] 는 a 의 (i − lowbit(i), i] 구간, 즉 i 에서 끝나고 길이가 lowbit(i) 인 구간의 합을 저장한다.

i:          1    2    3    4    5    6    7    8
lowbit:     1    2    1    4    1    2    1    8
맡는 구간: [1]  [1-2] [3] [1-4] [5] [5-6] [7] [1-8]

  tree[8] ████████████████████████████████  a[1..8]
  tree[4] ████████████████                  a[1..4]
  tree[6]                 ████████          a[5..6]
  tree[2] ████████                          a[1..2]
  tree[1] ████  tree[3] ████  tree[5] ████  tree[7] ████

누적 합: 맡은 구간만큼 건너뛰며 내려간다

prefix(i) = a[1] + … + a[i] 는 tree[i] 를 더하고, 그 구간 바로 앞인 i − lowbit(i) 로 건너뛰기를 0 이 될 때까지 반복한다. 한 번 건너뛸 때마다 최하위 1비트가 하나씩 지워지므로 반복 횟수는 i 의 1비트 개수, 많아야 log₂ n 이다.

prefix(7):  7 (0111) → 6 (0110) → 4 (0100) → 0
            tree[7] + tree[6] + tree[4]  =  a[7] + a[5..6] + a[1..4]

갱신: 나를 포함하는 칸들을 올라간다

a[i] += d 를 하려면 a[i] 를 구간에 포함하는 모든 칸을 고쳐야 한다. i += lowbit(i) 를 n 을 넘을 때까지 반복하면 정확히 그 칸들을 방문한다. 이번엔 최하위 비트에서 올림이 일어나며 위로 올라가고, 역시 O(log n) 이다.

add(3, d):  3 (0011) → 4 (0100) → 8 (1000) → 16 > n 이면 끝
            tree[3], tree[4], tree[8] 에 d 를 더함

구간 합

구간 [l, r] 의 합은 prefix(r) − prefix(l − 1) 이다. 빼기를 쓰므로, 펜윅 트리는 기본적으로 역연산이 있는 연산(합, XOR 등)에 쓴다. 최솟값처럼 역연산이 없는 질의는 앞 글의 세그먼트 트리가 맞다.

세그먼트 트리와 비교

항목 펜윅 트리 세그먼트 트리
메모리 n 칸 약 2n 칸 (재귀 구현은 최대 4n)
코드 길이 매우 짧음 길다
지원 연산 역연산 있는 연산 중심 (합, XOR) 결합 법칙만 있으면 (min, max, gcd 등)
구간 갱신 펜윅 두 개를 쓰는 기법으로 가능 게으른 전파
상수 작다 조금 크다

덤: 2차원

같은 아이디어를 행과 열에 각각 적용하면 2차원 펜윅 트리가 된다. 격자에서 점 갱신과 직사각형 합 질의를 O(log n · log m) 에 한다.

직접 해 보기

각 칸이 맡는 구간을 출력해 보고, 무작위 연산으로 정답과 대조한다.

import random

class Fenwick:
    """1-기반 펜윅 트리. tree[i] 는 (i - lowbit(i), i] 구간의 합."""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):            # a[i] += delta  (1 ≤ i ≤ n)
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i                 # 다음 책임 구간으로

    def prefix(self, i):                # a[1] + … + a[i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i                 # 맡은 구간만큼 건너뛰기
        return s

    def range_sum(self, l, r):          # a[l] + … + a[r]
        return self.prefix(r) - self.prefix(l - 1)

for i in [1, 2, 3, 4, 6, 8, 12]:
    lb = i & -i
    print(f"i={i:>2} ({i:04b})  lowbit={lb:>2}  tree[{i}] 는 a[{i-lb+1}..{i}] 의 합")

a = [0, 5, 2, 8, 1, 9, 3, 7, 4]        # a[0] 은 쓰지 않음
fw = Fenwick(8)
for i in range(1, 9):
    fw.add(i, a[i])
print("tree:", fw.tree[1:])
print("a[3..6] 합:", fw.range_sum(3, 6))
fw.add(4, 9)                            # a[4]: 1 → 10
print("갱신 후 a[3..6] 합:", fw.range_sum(3, 6))

rng = random.Random(0)
n = 500
arr = [0] * (n + 1)
f = Fenwick(n)
for _ in range(20_000):
    if rng.random() < 0.5:
        i, d = rng.randint(1, n), rng.randint(-50, 50)
        arr[i] += d; f.add(i, d)
    else:
        l = rng.randint(1, n); r = rng.randint(l, n)
        assert f.range_sum(l, r) == sum(arr[l:r + 1])
print("무작위 2만 연산 검증 통과")

i= 1 (0001)  lowbit= 1  tree[1] 는 a[1..1] 의 합
i= 2 (0010)  lowbit= 2  tree[2] 는 a[1..2] 의 합
i= 3 (0011)  lowbit= 1  tree[3] 는 a[3..3] 의 합
i= 4 (0100)  lowbit= 4  tree[4] 는 a[1..4] 의 합
i= 6 (0110)  lowbit= 2  tree[6] 는 a[5..6] 의 합
i= 8 (1000)  lowbit= 8  tree[8] 는 a[1..8] 의 합
i=12 (1100)  lowbit= 4  tree[12] 는 a[9..12] 의 합
tree: [5, 7, 8, 16, 9, 12, 7, 39]
a[3..6] 합: 21
갱신 후 a[3..6] 합: 30
무작위 2만 연산 검증 통과

앞 글 세그먼트 트리와 같은 데이터, 같은 질의를 썼다(이번엔 1-기반이라 [3..6] 이 앞 글의 [2,6) 과 같은 원소다). 결과도 21 → 30 으로 같다. tree 배열을 보면 tree[4] = 16 은 5+2+8+1, tree[8] = 39 는 전체 합이다. 세그먼트 트리의 노드 값 중 “왼쪽 자식”에 해당하는 것만 골라 담은 셈이라 n 칸으로 충분하다.

현업에서는

  • 순위와 백분위. 점수가 정수 범위로 정해진 리더보드에서 “이 점수보다 높은 사람 수”는 점수별 인원을 펜윅 트리에 담아 두면 prefix 한 번으로 나온다. 점수가 바뀌면 옛 점수 칸에 −1, 새 점수 칸에 +1 이다.
  • 빈도 기반 압축. 원래 목적대로 적응형 산술 부호화에서 기호 빈도를 갱신하고 누적 빈도를 조회하는 데 쓴다.
  • 역순 쌍 세기. 배열을 훑으며 “지금까지 본 값 중 나보다 큰 것의 수”를 펜윅 트리로 세면 O(n log n) 이다. 두 순위 목록이 얼마나 다른지(켄달 타우 거리) 재는 데 쓰인다.
  • 선택 기준. 합 계열이면 펜윅, 최솟값·최댓값이나 복잡한 결합 연산이면 세그먼트 트리, 갱신이 없으면 그냥 누적 합 배열. 가장 단순한 것부터 고른다.

확인 문제

  1. lowbit(40) 은? 그리고 tree[40] 은 어떤 구간의 합인가?
  2. n = 16 일 때 prefix(13) 은 어떤 칸들을 더하는가?
  3. n = 16 일 때 add(5, d) 는 어떤 칸들을 고치는가?
  4. 펜윅 트리로 구간 최솟값 질의를 그대로 하기 어려운 이유는?
  5. 펜윅 트리에서 인덱스를 1부터 쓰는 이유는?

풀이

  1. 40 = 0b101000 이므로 lowbit = 8. tree[40] 은 a[33..40] 의 합.
  2. 13 (1101) → 12 (1100) → 8 (1000) → 0. tree[13] + tree[12] + tree[8].
  3. 5 → 6 → 8 → 16. tree[5], tree[6], tree[8], tree[16].
  4. 구간 [l, r] 을 prefix(r) 과 prefix(l−1) 의 차로 구하는데, 최솟값에는 빼기 같은 역연산이 없다.
  5. lowbit(0) = 0 이라 0 에서는 건너뛰기가 진행되지 않아 무한 루프가 된다. 1부터 쓰면 모든 인덱스의 lowbit 이 1 이상이다.

더 읽을거리 (References)