Brain106. 펜윅 트리 / BIT (Fenwick Tree / Binary Indexed Tree)
핵심 인사이트 (3줄 요약)
- 본질: 펜윅 트리(Fenwick Tree 또는 Binary Indexed Tree, BIT)는 구간 합 쿼리와 포인트 업데이트를 O(log n) 시간에 수행하며, 세그먼트 트리보다 구현이 단순하고 메모리 사용량이 적은 자료구조이다.
- 가치: 구간 합만 필요할 때 세그먼트 트리보다 효율적이며, 특히累積 합(Cumulative Sum) 기반의统計処理에서 널리 사용된다.
- 융합: 데이터베이스 색인, 주식 차트 분석, 실시간 스트리밍 데이터 처리, 빈도数カウントなど 다양한领域에서 활용된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
펜윅 트리(Fenwick Tree)는 1989년 창립자 피터 M. 펜윅(Peter M. Fenwick)의 논문에서 처음 소개된 자료구조로, **바이너리 인덱스드 트리(Binary Indexed Tree, BIT)**라고도 불린다. 이 자료구조는 **구간 합(Range Sum Query)**과 **포인트 업데이트(Point Update)**를 모두 O(log n) 시간에 처리할 수 있다.
펜윅 트리가 중요한 이유는 효율성과 구현의 단순성 때문이다. 세그먼트 트리와 동일한 시간 복잡도를 가지면서도, 메모리 사용량이 적고 구현이 더 간단하다. 특히 구간 합만 필요하다면 펜윅 트리가最佳選擇이다.
펜윅 트리의 핵심 아이디어는 2진 표현의 특성을利用한다. 각 인덱스를 2진수로 표현하면, 해당 인덱스에 "소속된" 범위를 쉽게 계산할 수 있다. 예를 들어, 인덱스 12(2진수 1100)의 경우, 마지막 1비트(100)를 빼면 8이 되고, 이는 인덱스 12가 [9, 12] 범위를代表한다는 것을 의미한다. 이 특성을利用하여 O(log n) 시간에 쿼리와 업데이트를 수행한다.
[펜윅 트리 기본 원리]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [인덱스와 관리 구간] │
│ ──────────────────────────────────────────── │
│ │
│ 인덱스 1: [1, 1] → 관리 구간 길이 = 1 (2⁰) │
│ 인덱스 2: [1, 2] → 관리 구간 길이 = 2 (2¹) │
│ 인덱스 3: [3, 3] → 관리 구간 길이 = 1 (2⁰) │
│ 인덱스 4: [1, 4] → 관리 구간 길이 = 4 (2²) │
│ 인덱스 5: [5, 5] → 관리 구간 길이 = 1 (2⁰) │
│ 인덱스 6: [5, 6] → 관리 구간 길이 = 2 (2¹) │
│ 인덱스 7: [7, 7] → 관리 구간 길이 = 1 (2⁰) │
│ 인덱스 8: [1, 8] → 관리 구간 길이 = 8 (2³) │
│ │
│ [인덱스 6 (1100₂)의 예] │
│ ──────────────────────────────────────────── │
│ 6 = 1100₂ │
│ last set bit = 0100₂ (4) │
│ 6 - 4 = 2 │
│ → 인덱스 6은 [5, 6] (길이 4)의 합을 저장 │
│ │
│ [인덱스 12 (1100₂)의 예] │
│ ──────────────────────────────────────────── │
│ 12 = 1100₂ │
│ last set bit = 0100₂ (4) │
│ 12 - 4 = 8 │
│ → 인덱스 12은 [9, 12] (길이 4)의 합을 저장 │
│ │
│ [last set bit 계산: idx & (-idx)] │
│ ──────────────────────────────────────────── │
│ 양수: idx & (-idx) = 2진수에서 마지막 1비트의 값 │
│ 예: 12 & (-12) = 12 & 4 = 4 │
│ │
│ 12 = 01100₂ │
│ -12 = 10100₂ (2의 보수) │
│ 12 & (-12) = 00100₂ = 4 │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: 각 인덱스는 자신만의 관리 구간을 가지며, 그 구간들의 합으로 전체 배열을 표현한다.
- 원인: 2진수의 마지막 1비트가 해당 인덱스의 관리 구간 길이를 결정하기 때문이다.
- 결과: 쿼리와 업데이트 시 관리 구간들을 조합하여 O(log n) 시간을 달성한다.
- 판단: 구간 합만 필요하다면 펜윅 트리가 가장 효율적인 선택이다.
📢 섹션 요약 비유: 펜윅 트리는 물류 창고的系统과 같습니다. 각 창고에 특정区域的商品 수량을 저장하고, 어떤 구간의 총 수량을 알고 싶으면 해당区域들의 창고를 확인하면 됩니다. 각 창고가 관리하는区域의 크기가 2의 거듭제곱으로 설정되어 있어, 원하는区域을 빠르게 찾을 수 있습니다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
펜윅 트리의 핵심은 인덱스와 관리 구간 사이의 관계와 2진 인덱싱이다. 이 특성을 이해하면 쿼리와 업데이트 동작을 쉽게 이해할 수 있다.
트리 표현에서 펜윅 트리는 크기 n+1의 1차원 배열(보통 tree[]로 표기)로 구현된다. 인덱스는 1부터 시작하며(0은 사용하지 않음), 각 인덱스 i는 특정 범위의 합을 저장한다. 이 범위는 i - (i & (-i)) + 1부터 i까지이다.
**포인트 업데이트(Update)**는 특정 위치의 값을 delta만큼 변경하는操作이다. 동작 방식은 다음과 같다: 현재 인덱스 i의 tree[i]에 delta를 더한다. i에 i & (-i)를 더하여 다음 인덱스로 이동한다. i가 n보다 커질 때까지 반복한다. 이 과정에서 방문하는 인덱스 수는 O(log n)이다.
**前缀 합(Prefix Sum)**은 1부터 i까지의 합을 구하는 연산이다. 동작 방식은 다음과 같다: result에 tree[i]를 더한다. i에서 i & (-i)를 빼서 이전 인덱스로 이동한다. i가 0이 될 때까지 반복한다. 이 과정도 O(log n) 시간이 걸린다.
**구간 합(Range Sum)**은 left부터 right까지의 합을 계산한다. 이는 prefix(right) - prefix(left-1)으로 계산한다.
[펜윅 트리 연산 동작]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [포인트 업데이트: update(3, 5) - 인덱스 3에 5 더하기] │
│ ──────────────────────────────────────────── │
│ │
│ 원본 배열: [1, 3, 5, 7, 9, 11] │
│ tree[3] += 5 후 │
│ │
│ Step 1: tree[3] += 5 (3 = 11₂, last bit = 1) │
│ Step 2: i = 3 + (3 & -3) = 3 + 1 = 4 → tree[4] += 5 │
│ Step 3: i = 4 + (4 & -4) = 4 + 4 = 8 > n → 종료 │
│ │
│ 영향받은 트리 노드: 3, 4 │
│ │
│ [前缀 합: prefix_sum(7) 계산] │
│ ──────────────────────────────────────────── │
│ │
│ Step 1: i = 7 → result += tree[7], i = 7 - (7 & -7) = 7-1=6│
│ Step 2: i = 6 → result += tree[6], i = 6 - (6 & -6) = 6-2=4│
│ Step 3: i = 4 → result += tree[4], i = 4 - (4 & -4) = 4-4=0│
│ Step 4: i = 0 → 종료 │
│ │
│ 방문한 노드: 7, 6, 4 │
│ │
│ [구간 합: range_sum(2, 5) = prefix(5) - prefix(1)] │
│ ──────────────────────────────────────────── │
│ prefix(5): 노드 5, 4 방문 │
│ prefix(1): 노드 1 방문 │
│ 최종: prefix(5) - prefix(1) = tree[5] + tree[4] - tree[1] │
│ │
│ [펜윅 트리 구성: build 예시] │
│ ──────────────────────────────────────────── │
│ 배열: [1, 3, 5, 7, 9, 11] │
│ │
│ for i = 1 to n: │
│ tree[i] = 0 │
│ for i = 1 to n: │
│ update(i, arr[i]) # 각 요소를 추가 │
│ │
│ 또는 직접 구성: │
│ for i = 1 to n: │
│ tree[i] = arr[i] │
│ for i = 1 to n: │
│ j = i + (i & -i) │
│ if j <= n: │
│ tree[j] += tree[i] │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: 업데이트와 쿼리 모두 O(log n) 시간에 수행된다.
- 원인: 인덱스 변경 시 마지막 1비트의 값만큼 점프하기 때문이다.
- 결과: 2진 트리 구조에서의 경로 길이가 log n이다.
- 판단: 이 특성을 이해하면 펜윅 트리의 동작을 직관적으로把握할 수 있다.
Ⅲ. 구현 및 활용 (Implementation & Applications)
펜윅 트리의 구현은 매우简洁하여 실전에서 널리 사용된다. 기본 구현은 50줄 이하로 가능하며, 다양한 확장이 가능하다.
기본 구현에서 BIT 클래스는 크기 n의 배열과 tree[]를 가진다. update(i, delta)는 인덱스 i에 delta를 더하고, query(i)는 1부터 i까지의前缀 합을 반환한다. range_query(l, r)는 query(r) - query(l-1)로 구현한다.
확장된 활용으로 2D 펜윅 트리는 2차원 배열에서 구간 합을 O((log n)²) 시간에 처리한다. 구간 업데이트, 포인트 쿼리는 다른 BIT를 함께 사용하여实现할 수 있다. 구간 업데이트, 구간 쿼리는 두 BIT를 사용하여 구현한다. 이는 "累積 합의 累積 합" 기법이다.
활용 사례로 동적 빈도数カウント에서 데이터가 실시간으로 추가될 때 빈도수를 추적하는 데 사용된다. 股票市場の分析에서 이동 평균, 누적 거래량 등에 활용된다. データ 스트리밍에서 실시간으로 들어오는 데이터의 sliding window 합을 구하는 데 사용된다. ランキング 시스템에서 점수 변화에 따른 순위 변경을 추적하는 데 활용된다.
[펜윅 트리 구현 코드]
┌──────────────────────────────────────────────────────────────┐
│ │
│ class FenwickTree: │
│ def __init__(self, n): │
│ self.n = n │
│ self.tree = [0] * (n + 1) │
│ │
│ # 인덱스 i에 delta만큼 더하기 │
│ def update(self, i, delta): │
│ while i <= self.n: │
│ self.tree[i] += delta │
│ i += i & (-i) │
│ │
│ # 1부터 i까지의 합 (prefix sum) │
│ def query(self, i): │
│ result = 0 │
│ while i > 0: │
│ result += self.tree[i] │
│ i -= i & (-i) │
│ return result │
│ │
│ # 구간 [l, r]의 합 │
│ def range_query(self, l, r): │
│ if l > r: │
│ return 0 │
│ return self.query(r) - self.query(l - 1) │
│ │
│ # 배열로 초기화 │
│ def build(self, arr): │
│ for i in range(1, self.n + 1): │
│ self.tree[i] = arr[i-1] │
│ for i in range(1, self.n + 1): │
│ j = i + (i & -i) │
│ if j <= self.n: │
│ self.tree[j] += self.tree[i] │
│ │
│ [2D Fenwick Tree] │
│ ──────────────────────────────────────────── │
│ class FenwickTree2D: │
│ def __init__(self, rows, cols): │
│ self.rows = rows │
│ self.cols = cols │
│ self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]│
│ │
│ def update(self, x, y, delta): │
│ i = x │
│ while i <= self.rows: │
│ j = y │
│ while j <= self.cols: │
│ self.tree[i][j] += delta │
│ j += j & (-j) │
│ i += i & (-i) │
│ │
│ def query(self, x, y): │
│ result = 0 │
│ i = x │
│ while i > 0: │
│ j = y │
│ while j > 0: │
│ result += self.tree[i][j] │
│ j -= j & (-j) │
│ i -= i & (-i) │
│ return result │
│ │
│ def range_query(self, x1, y1, x2, y2): │
│ return (self.query(x2, y2) │
│ - self.query(x1-1, y2) │
│ - self.query(x2, y1-1) │
│ + self.query(x1-1, y1-1)) │
│ │
│ [구간 업데이트, 구간 쿼리용 BIT 두 개 사용] │
│ ──────────────────────────────────────────── │
│ BIT1: 원본 값 저장 │
│ BIT2: 원본 값 * 인덱스 저장 │
│ │
│ prefix_sum(i) = query(BIT1, i) * i - query(BIT2, i) │
│ range_sum(l, r) = prefix_sum(r) - prefix_sum(l-1) │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: 펜윅 트리의 기본 구현은 매우 간단하고 효율적이다.
- 원인: 2진 인덱싱의 수학적 특성 덕분이다.
- 결과: 실제 시스템에서도 널리 사용되는 신뢰할 수 있는 자료구조이다.
- 판단: 구간 합만 필요하다면 세그먼트 트리보다 펜윅 트리를 우선 고려한다.
Ⅳ. 세그먼트 트리와의 비교 및 선택 기준 (Comparison & Selection Criteria)
펜윅 트리와 세그먼트 트리는 both 구간 쿼리 문제를 해결하지만, 각각 다른 장단점을 가진다. 상황에 맞게 적절한 자료구조를 선택하는 것이 중요하다.
공통점으로 both 포인트 업데이트와 구간 쿼리를 O(log n) 시간에 지원한다. 둘 다 배열 기반으로 구현된다. 그리고 둘 다 동적 데이터 처리 가능하다.
펜윅 트리 장점으로 메모리 효율적 (n+1 vs 4n), 구현이 단순 (핵심 연산이 2줄), 상수 계수가 작음 (실제 실행이稍快), 코드 길이가 짧음이 있다.
펜윅 트리 단점으로 구간 합만 가능 (다른 연산은 직접 구현 어려움), 구간 업데이트 미지원 (별도 구현 필요), 확장성이 제한적이다.
세그먼트 트리 장점으로 다양한 연산 지원 (합, 최솟값, 최댓값, GCD 등), 구간 업데이트 용이 (Lazy Propagation), 더 범용적이다.
세그먼트 트리 단점으로 메모리 사용량 많음 (4n), 구현이稍微 복잡, 상수 계수가 큼 (log n의 계수).
[펜윅 트리 vs 세그먼트 트리]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [선택 기준표] │
│ ──────────────────────────────────────────── │
│ │
│ 상황 권장 자료구조 │
│ ──────────────────────────────────────────── │
│ 구간 합만 필요 Fenwick Tree │
│ 구간 최솟값/최댓값 필요 Segment Tree │
│ 구간 업데이트 필요 Segment Tree (Lazy) │
│ 메모리 엄격 제한 Fenwick Tree │
│ 코드 복잡도 낮춤 Fenwick Tree │
│ 다양한 연산 필요 Segment Tree │
│ │
│ [예시: 어떤 자료구조를 선택할까?] │
│ ──────────────────────────────────────────── │
│ │
│ Q1. 구간 합 + 구간 업데이트 필요? → 세그먼트 트리 │
│ Q2. 구간 합만 필요, 메모리 절약? → Fenwick Tree │
│ Q3. 구간 합 + 최솟값 필요? → 세그먼트 트리 │
│ Q4. 2D 구간 합 필요? → 2D Fenwick Tree 또는 │
│ 2D 세그먼트 트리 │
│ │
│ [성능 비교 (구간 합 쿼리)] │
│ ──────────────────────────────────────────── │
│ n = 1,000,000인 경우 │
│ Fenwick Tree: ≈ 20 연산 (log₂ 1,000,000 ≈ 20) │
│ Segment Tree: ≈ 40 연산 (2 * log₂ 1,000,000 ≈ 40) │
│ (각 연산이 더 많고 상수 계수도 더 큼) │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: 대부분의 경우 Fenwick Tree가 더 효율적이다.
- 원인: 더 적은 메모리와 더 작은 상수 계수 때문이다.
- 결과: 구간 합만 필요하다면 Fenwick Tree를 기본으로 선택한다.
- 판단: 향후 요구사항 변경 가능성을 고려하여 초기 선택을 결정해야 한다.
Ⅴ. 요약 및 점검 (Summary & Checklist)
펜윅 트리(Fenwick Tree, BIT)는 2진 인덱싱을利用한 구간 합 자료구조로, O(log n) 시간에 쿼리와 업데이트를 수행하며 메모리 효율이 좋다. 특히 구간 합만 필요한 경우 세그먼트 트리보다優れている.
핵심 점검 사항으로 먼저, 핵심 원리에서 2진수의 마지막 1비트가 관리 구간을 결정한다. 둘째, 시간 복잡도에서 구성 O(n) 또는 O(n log n), 쿼리 O(log n), 업데이트 O(log n)이다. 셋째, 핵심 연산으로 update(i, delta)와 query(i)가 있다. 넷째, 구간 합은 query(r) - query(l-1)로 계산한다. 다섯째, 세그먼트 트리 비교에서 Fenwick Tree는 구간 합에 특화되어 더 효율적이다. 여섯째, 확장으로 2D BIT, 구간 업데이트용 BIT 등이 있다.
핵심 용어 정리
- 펜윅 트리 (Fenwick Tree): 2진 인덱싱 기반 구간 합 자료구조
- BINARY INDEXED TREE (BIT): 펜윅 트리의 영문 이름
- 2진 인덱싱 (Binary Indexed): 인덱스의 2진 표현을利用하는 기법
- last set bit: 정수에서 가장 오른쪽에 있는 1비트
- 前缀 합 (Prefix Sum): 1부터 i까지의 누적 합
检查清单 (Checkpoint)
- 펜윅 트리가 2진 인덱싱을 어떻게 활용하는지 설명할 수 있는가?
- update()와 query() 함수의 동작 과정을 설명할 수 있는가?
- 펜윅 트리와 세그먼트 트리의 장단점을 비교할 수 있는가?
- 구간 합을 어떻게 계산하는지 설명할 수 있는가?
- 2D 펜윅 트리가 무엇인지 알고 있는가?
- 구간 업데이트에 펜윅 트리를 어떻게 적용할 수 있는지 알고 있는가?