ds · 13

펜윅 트리(BIT)

BIT구간합트리

배열의 앞에서부터 i번째까지의 합(누적 합)은 값이 바뀌지 않는다면 미리 계산한 누적 합 배열로 O(1)에 답할 수 있습니다. 하지만 값이 자주 바뀌면 누적 합 배열 전체를 다시 계산해야 해서 갱신이 O(n)입니다. 펜윅 트리(Fenwick tree, 이진 인덱스 트리 BIT)는 누적 합 쿼리와 값 갱신을 모두 O(log n)에 처리하는 자료구조로, 코드가 짧고 크기 n의 배열 하나만 쓴다는 점이 특징입니다.

핵심 아이디어는 인덱스 i의 칸이 i의 가장 낮은 1비트(lowbit, i & -i)만큼의 길이를 담당하게 하는 것입니다. 예를 들어 i = 12(2진수 1100)는 lowbit가 4여서 A[9]부터 A[12]까지의 합을 저장합니다. 누적 합은 i에서 lowbit를 빼며 칸을 모으고, 값 갱신은 lowbit를 더하며 칸을 고칩니다. 이 토픽에서는 각 칸이 담당하는 구간, 누적 합을 구하는 경로, 값을 바꿀 때 고치는 칸을 단계별로 봅니다.

핵심 개념

lowbit

정수 i의 가장 낮은 1비트만 남긴 값으로 i & -i로 구합니다. 12(1100)의 lowbit는 4, 11(1011)의 lowbit는 1입니다.

핵심 개념

칸이 담당하는 구간

BIT[i]는 A[i - lowbit(i) + 1]부터 A[i]까지의 합을 저장합니다. 칸 수는 배열과 같은 n개이고 인덱스는 1부터 시작합니다.

핵심 개념

누적 합 쿼리

i에서 시작해 BIT[i]를 더하고 i에서 lowbit를 빼는 일을 0이 될 때까지 반복합니다. 거치는 칸의 구간이 서로 겹치지 않고 1부터 i까지를 정확히 채웁니다.

핵심 개념

점 갱신

A[i]에 값을 더하려면 i에서 시작해 BIT[i]에 더하고 i에 lowbit를 더하는 일을 n을 넘을 때까지 반복합니다. A[i]를 포함하는 구간의 칸만 고칩니다.

핵심 개념

구간 합

구간 [l, r]의 합은 누적 합 두 개의 차 prefix(r) - prefix(l - 1)로 구합니다. 빼서 되돌릴 수 있는 연산(합, XOR 등)에서만 쓸 수 있는 방식입니다.

핵심 개념

차이 배열 확장

차이 배열을 펜윅 트리로 관리하면 구간 전체에 값을 더하고 한 점의 값을 읽는 연산도 O(log n)에 처리할 수 있습니다.

쿼리와 갱신이 모두 O(log n)입니다 — 빼든 더하든 이동할 때마다 lowbit가 적어도 두 배가 되므로 거치는 칸은 최대 floor(log2 n) + 1개입니다. 원소를 하나씩 update하면 구축이 O(n log n)이지만, i + lowbit(i) 칸으로 값을 올려 보내는 방식은 O(n)에 구축합니다.

세그먼트 트리보다 가볍습니다 — 세그먼트 트리도 보통 배열로 구현하지만 2n~4n칸이 필요한 반면, 펜윅 트리는 크기 n 배열 하나로 되고 코드도 짧습니다. 대신 지원하는 연산이 합처럼 역연산이 있는 것으로 제한됩니다.

비트 연산이 트리를 대신합니다 — 부모와 자식을 가리키는 포인터 없이 i & -i만으로 다음 칸을 찾습니다. 트리 구조는 인덱스의 2진수 표현 속에 들어 있습니다.

인덱스는 1부터입니다 — i = 0이면 lowbit가 0이어서 갱신 반복이 멈추지 않으므로(prefix는 곧바로 끝나 0을 돌려줍니다) i & -i 방식에서는 인덱스를 1부터 쓰는 것이 관례입니다. 0부터 시작하는 입력은 1을 더해서 씁니다.

이 시각화에서 확인할 것 — "구조" 탭에서 칸마다 담당하는 구간을, "구간 합" 탭에서 거치는 칸을, "값 갱신" 탭에서 고치는 칸을 STEP으로 확인하세요.

펜윅 트리의 배경

펜윅 트리는 피터 펜윅(Peter M. Fenwick)이 1994년 논문 "A new data structure for cumulative frequency tables"에서 소개했습니다. 논문에서는 이 구조를 이진 인덱스 트리(Binary Indexed Tree, BIT)라고 불렀습니다. 압축 알고리즘에서 기호의 누적 빈도를 빠르게 구하고 갱신하는 문제에서 출발했고, 지금은 저자 이름을 붙여 펜윅 트리라고도 부릅니다.

숫자로 확인하기

칸의 구간 — 배열 길이 12에서 BIT[12]는 A[9]~A[12](lowbit 4)를, BIT[8]은 A[1]~A[8](lowbit 8)을, BIT[11]은 A[11] 하나(lowbit 1)를 담당합니다. 칸 12개가 배열 12개와 같은 크기입니다.

누적 합 prefix(11) — 11 → 10 → 8 → 0으로 이동하며 BIT[11] + BIT[10] + BIT[8] = 2 + 5 + 26 = 33을 얻습니다. A[1]~A[11]의 11개를 더하지 않고 칸 3개만 읽습니다.

구간 합 [4, 9] — prefix(9) - prefix(3) = 27 - 10 = 17로, A[4]~A[9]의 합 1 + 4 + 2 + 6 + 3 + 1 = 17과 같습니다.

값 갱신 — A[5]에 3을 더하면 5 → 6 → 8로 이동하며 칸 3개(4→7, 6→9, 26→29)를 고치고, 다음은 16이 되어 n = 12를 넘어 끝납니다.

자주 하는 오해

BIT[i]는 배열의 i번째 값이다 — BIT[i]는 A[i] 하나가 아니라 lowbit(i)개 원소의 합입니다. lowbit가 1인 홀수 칸만 원소 하나와 같습니다.

세그먼트 트리를 완전히 대체한다 — 구간 합과 점 갱신에는 간결하지만, 구간 최솟값처럼 빼서 되돌릴 수 없는 연산은 기본 구조로 처리하기 어렵습니다. 그런 경우에는 세그먼트 트리를 씁니다.

이진 트리를 따로 만든다 — 노드나 포인터를 만들지 않고 배열 하나만 씁니다. 이름에 "트리"가 들어간 것은 칸들의 의존 관계가 트리 모양이기 때문입니다.

인덱스를 0부터 써도 된다 — i = 0에서는 i & -i가 0이라 갱신이 끝나지 않거나 아무 칸도 건드리지 못하므로, 이 방식에서는 인덱스를 1부터 쓰도록 맞춥니다. 0부터 쓰는 변형도 있지만 i & (i + 1), i | (i + 1) 같은 다른 식을 씁니다.

면접에서 이렇게 물어요

면접 질문

펜윅 트리는 어떻게 동작하나요?

칸 i가 i의 lowbit 길이의 구간 합을 저장합니다. 누적 합은 i에서 lowbit를 빼며 거친 칸을 더하고, 갱신은 lowbit를 더하며 거친 칸에 값을 더해 둘 다 O(log n)입니다.

면접 질문

lowbit는 어떻게 구하고 왜 되나요?

i & -i로 구합니다. 2의 보수에서 -i는 i의 가장 낮은 1비트 위쪽 비트를 모두 뒤집은 값이라, i와 AND하면 가장 낮은 1비트만 남습니다.

면접 질문

세그먼트 트리와 비교하면?

펜윅 트리는 코드가 짧고 크기 n 배열 하나만 씁니다. 세그먼트 트리는 2n~4n칸이 필요하지만 최솟값 같은 다양한 연산과 지연 전파를 지원합니다. 합과 점 갱신이면 펜윅 트리가 간결합니다.

면접 질문

구간 합은 어떻게 구하나요?

prefix(r) - prefix(l - 1)로 누적 합 두 개를 빼서 구합니다. 각각 O(log n)이므로 구간 합도 O(log n)입니다.

활용 사례

알고리즘 대회 — 구간 합과 역순 쌍(inversion) 세기 같은 문제에서 짧은 코드로 O(log n)을 얻는 도구로 쓰입니다.

누적 빈도 계산 — 펜윅이 처음 제안한 용도로, 압축 알고리즘의 기호 누적 빈도처럼 값이 계속 바뀌는 분포의 누적 합을 구하는 데 씁니다.

2차원 확장 — 펜윅 트리를 2차원으로 겹쳐 격자 영역의 합을 구하고 점을 갱신하는 구조로도 확장됩니다.

함께 보면 좋은 토픽

구간 트리(세그먼트 트리) — 합 이외의 연산까지 처리하는 더 일반적인 구간 쿼리 구조를 봅니다.

시간 복잡도 — O(n)과 O(log n)의 차이를 봅니다.

배열과 연결 리스트 — 펜윅 트리가 얹히는 배열 구조를 봅니다.

힙 — 배열 인덱스 계산으로 트리를 표현하는 또 다른 예를 봅니다.

참고 자료

논문 — Fenwick, P. M., "A new data structure for cumulative frequency tables", Software: Practice and Experience 24(3), 327-336쪽, 1994

학습 자료 — cp-algorithms Fenwick Tree

Python — 펜윅 트리 기본 구현

class BIT:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # 인덱스는 1부터 쓴다

    def update(self, i, delta):       # A[i]에 delta를 더한다
        while i <= self.n:
            self.t[i] += delta
            i += i & -i                  # lowbit를 더해 위로 이동

    def prefix(self, i):              # A[1] ~ A[i]의 합
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i                  # lowbit를 빼 앞으로 이동
        return s

    def range_sum(self, l, r):         # A[l] ~ A[r]의 합
        return self.prefix(r) - self.prefix(l - 1)

A = [3, 2, 5, 1, 4, 2, 6, 3, 1, 4, 2, 5]
bit = BIT(len(A))
for i, v in enumerate(A, 1):
    bit.update(i, v)
print(bit.t[1:])                        # [3, 5, 5, 11, 4, 6, 6, 26, 1, 5, 2, 12]
print(bit.prefix(11), bit.range_sum(4, 9))   # 33 17
bit.update(5, 3)
print(bit.t[5], bit.t[6], bit.t[8], bit.prefix(11))  # 7 9 29 36

i & -i는 i의 가장 낮은 1비트 lowbit를 구하는 관용구입니다. 음수를 2의 보수로 표현하는 컴퓨터에서 -i는 i의 가장 낮은 1비트 위쪽 비트를 모두 뒤집은 값이어서, i와 AND하면 가장 낮은 1비트 하나만 남습니다. 칸 t[i]가 담당하는 구간의 길이가 이 lowbit입니다. prefix는 i에서 lowbit를 빼며 0이 될 때까지 거치는 칸을 더하고, update는 lowbit를 더하며 n을 넘을 때까지 거치는 칸을 고칩니다. 둘 다 최대 약 log2(n)번 반복하므로 O(log n)이며, 시각화의 구간 합 탭과 값 갱신 탭이 따라가는 경로와 같습니다. 구간 합은 누적 합 두 개의 차이므로 prefix(r) - prefix(l - 1)로 구합니다. 이 방식은 합처럼 빼서 되돌릴 수 있는 연산에서만 가능하다는 점이 기본 펜윅 트리의 제약입니다.

Python — lowbit 확인과 O(n) 구축

def lowbit(i): return i & -i

for i in (11, 12):
    print(i, bin(i), lowbit(i), i - lowbit(i) + 1, i)
# 11 0b1011 1 11 11   -> BIT[11]은 A[11~11]
# 12 0b1100 4 9 12    -> BIT[12]는 A[9~12]

def build(arr):                      # 원소를 하나씩 update하지 않고 O(n)에 구축
    n = len(arr)
    t = [0] + list(arr)
    for i in range(1, n + 1):
        j = i + (i & -i)                 # i를 포함하는 바로 위 칸
        if j <= n:
            t[j] += t[i]
    return t

print(build(A)[1:])                 # [3, 5, 5, 11, 4, 6, 6, 26, 1, 5, 2, 12]

i = 12는 2진수 1100이고 lowbit는 4이므로 BIT[12]는 12에서 앞으로 4개인 A[9]부터 A[12]까지의 합을 저장합니다. i = 11은 1011이고 lowbit가 1이어서 BIT[11]은 A[11] 하나만 담당합니다. 시각화의 구조 탭에서 본 구간과 같습니다. 원소를 n번 update하면 O(n log n)이지만, build는 각 칸의 값을 자기를 포함하는 바로 위 칸(i + lowbit(i))에 한 번씩 더해 O(n)에 같은 트리를 만듭니다. 아래쪽 칸이 먼저 완성된 값을 위로 올려 보내는 방식입니다. 원소를 하나씩 update해 만든 BIT와 build가 만든 BIT는 같은 배열이며, 위 두 코드의 출력도 같습니다.

Python — 구간 더하기와 한 점 값 읽기

class RangeAddBIT:
    def __init__(self, n):
        self.b = BIT(n)                  # 차이 배열을 펜윅 트리로 관리

    def range_add(self, l, r, v):      # A[l] ~ A[r]에 v를 더한다
        self.b.update(l, v)
        if r + 1 <= self.b.n:
            self.b.update(r + 1, -v)

    def get(self, i):                  # A[i]의 현재 값
        return self.b.prefix(i)

rb = RangeAddBIT(10)
rb.range_add(3, 7, 5)
print([rb.get(i) for i in range(1, 11)])   # [0, 0, 5, 5, 5, 5, 5, 0, 0, 0]

구간 전체에 같은 값을 더하는 연산도 차이 배열을 펜윅 트리에 넣으면 O(log n)에 할 수 있습니다. 0으로 시작한 배열에서 차이 배열은 인접한 원소의 차이를 저장하므로, 구간 [l, r]에 v를 더하는 일은 l 위치에 +v, r + 1 위치에 -v를 더하는 점 갱신 두 번으로 바뀝니다. 어떤 위치의 값은 차이 배열의 누적 합이므로 prefix로 읽습니다. 예에서 구간 [3, 7]에 5를 더하면 3번부터 7번까지만 5가 되고 나머지는 0으로 남습니다. 이 구조는 구간 더하기와 한 점 읽기만 지원합니다. 구간 더하기와 구간 합을 함께 처리하려면 펜윅 트리 두 개를 쓰는 확장이나 지연 전파가 있는 세그먼트 트리를 씁니다.

펜윅 트리(BIT)에서 인덱스 i가 담당하는 구간의 길이를 결정하는 값은?

비트 연산으로 구합니다.

펜윅 트리의 i번째 칸은 i의 최하위 1비트(lowbit = i & -i)만큼의 길이를 담당합니다. 예를 들어 i=12(1100)의 lowbit는 4이므로 원소 9~12를 합쳐서 저장합니다.

펜윅 트리에서 1부터 i까지의 구간 합을 구하는 시간 복잡도는?

i에서 lowbit를 빼며 내려갑니다.

구간 합 쿼리는 i에서 시작해 lowbit를 반복해서 빼며 이동하므로 최대 log n번 반복합니다. 값 갱신도 lowbit를 더하며 올라가므로 O(log n)입니다.

펜윅 트리가 세그먼트 트리보다 유리한 점은?

대신 지원하는 연산의 종류에는 제약이 있습니다.

펜윅 트리는 코드가 짧고 크기 n의 배열 하나만 필요해 메모리도 적게 씁니다. 다만 구간 합처럼 역연산이 가능한 연산에 주로 쓰이고, 구간 최솟값 같은 연산은 세그먼트 트리가 더 적합합니다.