segment tree와 Fenwick tree(BIT)는 어떻게 빠른 범위 질의를 지원하나요?

Question

Accepted Answer

**segment tree(세그먼트 트리)**와 **Fenwick tree(Binary Indexed Tree, BIT)**는 둘 다 **범위 질의**(예: `[l, r]`에 대한 합)와 **점 갱신(point update)**을 **O(log n)**에 답합니다. 단순 스캔의 O(n)이나 prefix-sum array의 O(n) 갱신과 대비됩니다.

## 이들이 해결하는 문제

```text
array + 많은 "범위 [l,r]의 합" 및 "인덱스 i 갱신" 호출:
  단순 prefix sum: 질의 O(1)이지만 갱신은 O(n)
  segment/Fenwick: 질의 O(log n) 그리고 갱신 O(log n)
```

## Fenwick tree(BIT) — 간결하고 우아함

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # 다음 담당 노드로 점프
    def prefix(self, i):               # [0..i]의 합, O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## Segment tree — 더 일반적

segment tree는 array 구간별 집계를 이진 트리에 저장하여, **임의의 결합 연산(associative operation)**(합, 최소, 최대, gcd)을 지원하고, 지연 전파(lazy propagation)를 쓰면 **범위 갱신**도 지원합니다.

```text
        [0..7] 합
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... 단일 원소까지
```

## 비교

| | Fenwick (BIT) | Segment tree |
|---|---|---|
| 질의 / 갱신 | O(log n) | O(log n) |
| 공간 | O(n) | O(2n) |
| 연산 | 합(역연산 가능) | 임의의 결합 연산 |
| 범위 갱신 | 더 어려움 | 쉬움(지연 전파) |
| 코드 크기 | 아주 작음 | 더 큼 |

## 왜 중요한가

이 구조들은 "값을 갱신한 뒤 범위에 대한 집계를 질의하는" 것을 빠르게 만듭니다. 경쟁 프로그래밍, 분석 윈도우, 구간 문제에 필수적입니다.

둘 중 선택은 트레이드오프입니다. Fenwick tree는 합에 대해 아주 작고 빠르며, segment tree는 min/max/범위 갱신 작업에 더 유연합니다.

	Fenwick (BIT)	Segment tree
질의 / 갱신	O(log n)	O(log n)
공간	O(n)	O(2n)
연산	합(역연산 가능)	임의의 결합 연산
범위 갱신	더 어려움	쉬움(지연 전파)
코드 크기	아주 작음	더 큼