펜윅 트리(Fenwick Tree) aka BIT 완전 정리: 개념, 구현, 세그먼트 트리와 차이점 비교

펜윅 트리(Fenwick Tree) aka BIT 완전 정리: 개념, 구현, 세그먼트 트리와 차이점 비교

**펜윅 트리(Fenwick Tree)**는 **Binary Indexed Tree (BIT)**라고도 불리며,
배열에서 구간 합을 빠르게 처리하기 위한 자료구조입니다.
구간 합 구하기, 누적합 업데이트가 핵심이며,
세그먼트 트리보다 간단하고 메모리 효율적이어서 실전에서 많이 쓰입니다.

이번 글에서는 Fenwick Tree의 원리, 구현법, 주요 연산,
그리고 세그먼트 트리와의 차이점과 문제 적용까지 상세히 알아봅니다.

---

✅ 펜윅 트리란?

정수 배열에서 누적합을 빠르게 구하거나 갱신할 수 있도록 설계된 자료구조
**시간 복잡도 O(log N)**로 쿼리 및 업데이트가 가능

---

🔍 구조 개념 (Binary Indexed Tree)

• 배열의 각 인덱스는 특정 범위의 구간 합을 담당합니다.
• 이 구조는 인덱스의 2진수 표현에서 가장 낮은 비트를 활용하여 구현합니다.

예:
idx = 6 (110₂) → 담당 구간 = [5~6], tree[6]은 arr[5] + arr[6]

---

⏱ 시간 복잡도

연산 복잡도

구간 합	O(log N)
값 업데이트	O(log N)
전체 초기화	O(N log N)

---

🛠 Python 구현 (1-based index)

class FenwickTree:
    def __init__(self, size):
        self.N = size
        self.tree = [0] * (self.N + 1)

    def update(self, i, diff):
        while i <= self.N:
            self.tree[i] += diff
            i += (i & -i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= (i & -i)
        return res

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

---

✅ 사용 예시

반응형

arr = [0, 3, 2, -1, 6, 5, 4, -3, 3]  # 1-based (0번 무시)
ft = FenwickTree(len(arr) - 1)

# 초기화
for i in range(1, len(arr)):
    ft.update(i, arr[i])

# 1 ~ 5까지 합
print(ft.range_query(1, 5))  # 출력: 3+2+(-1)+6+5 = 15

# 4번 원소 +2
ft.update(4, 2)
print(ft.range_query(1, 5))  # 출력: 17

---

📘 세그먼트 트리 vs 펜윅 트리 비교

항목 세그먼트 트리 펜윅 트리 (BIT)

구현 복잡도	복잡	✅ 단순
메모리 사용량	4N	✅ N + 1
지원 연산	다양 (최솟값, 최대값 등)	제한적 (누적합 중심)
구간 합	✅ O(log N)	✅ O(log N)
구간 갱신 (range update)	Lazy 필요	❌ 불가 (확장 필요)
코드 길이	긴 편	✅ 매우 짧음

📌 정리

• 단순 누적합 → BIT
• 다양한 쿼리/구간 갱신 → Segment Tree

---

🔄 확장형 BIT

확장 유형 설명

Range Update / Point Query	차 배열 사용
2D BIT	행렬의 누적합 처리 가능
K차원 BIT	드물지만 확장 가능 (좌표압축 활용)

---

📘 실전 문제 (백준)

문제 번호 제목 내용

2042	구간 합 구하기	세그먼트 트리 or BIT 가능
11659	구간 합 구하기 4	누적합, BIT 적용 쉬움
1395	스위치	BIT 응용 어려움
10999	구간 합 구하기 2	구간 갱신은 BIT X

---

📌 결론 및 요약

• 펜윅 트리는 누적합/포인트 업데이트 중심의 자료구조로,
  간단하고 빠르며 메모리 효율적
• 단, 구간 갱신 등 복잡한 연산은 세그먼트 트리에 맡기는 것이 좋음
• 코딩 테스트에서 자주 등장하며, 간단한 누적합 문제에 매우 적합

👉 다음 글에서는 **2차원 펜윅 트리(2D BIT)**의 구조와
이미지 누적합, 구간 쿼리 처리 등 실전 응용 문제를 다뤄보겠습니다.

---

📚 참고자료 및 출처

• 백준 11659, 2042
• TopCoder Tutorial – Fenwick Tree
• CP-Algorithms – Fenwick Tree

---

 

펜윅트리, Binary Indexed Tree, BIT, 누적합, 구간합, 파이썬 알고리즘, 세그먼트트리 비교, 코딩테스트 누적합, 자료구조 최적화, SEO 최적화 10개