Segment Tree와 Fenwick Tree로 범위 질의 최적화하기
Segment Tree와 Fenwick Tree를 활용해 범위 질의와 구간 업데이트를 최적화하는 방법, Lazy Propagation과 구현 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
범위 연산이 반복될 때 필요한 트리 구조
대규모 배열에서 구간 합, 최댓값, 증분 업데이트를 밀리초 단위로 처리하려면 배열을 매번 순회하는 방식으로는 한계가 있다. Segment Tree와 Fenwick Tree(Binary Indexed Tree)는 범위 질의와 업데이트를 로그 시간 안에 처리하기 위해 쓰는 대표적인 구조다.
범위 질의는 배열의 [l, r] 구간을 대상으로 합·최댓값·최솟값 같은 집계를 구하는 연산이다. 두 구조는 모두 이 문제를 다루지만, 지원하는 연산의 폭과 구현 복잡도는 다르다.
Segment Tree는 구간을 나눈 완전 이진 트리다. 각 노드는 자신이 맡은 구간의 집계값을 보관하며, 업데이트와 질의를 모두 O(log N)에 처리한다. 합뿐 아니라 최댓값, 최솟값처럼 모노이드 연산을 적용할 수 있고, Lazy Propagation을 조합하면 구간 단위 갱신도 다룰 수 있다.
Fenwick Tree는 프리픽스 합을 중심으로 동작하는 트리형 배열이다. 구현과 메모리 사용이 비교적 단순하며, 업데이트와 질의는 O(log N)이다. 기본 형태는 point add와 prefix sum에 맞지만, 두 트리를 함께 쓰면 range add와 range sum까지 확장할 수 있다.
지연 전파와 lowbit가 처리 범위를 나누는 방식
Segment Tree의 노드는 구간 [l, r], 집계값 value, 지연 태그 lazy를 가진다. 업데이트가 특정 노드의 구간 전체를 덮으면 자식으로 즉시 내려가지 않고 해당 노드에 lazy 값을 누적한다. 이후 자식 정보가 필요해질 때만 지연 값을 전파한다.
이 방식은 구간 업데이트 요청에서 불필요한 전파를 줄인다. 질의 중에는 lazy가 반영된 값을 반환하고, 범위 밖 구간은 즉시 가지치기한다. 비겹침 구간의 반환값은 합에서는 0, 최댓값에서는 -∞처럼 연산에 맞춰 정해야 한다.
Fenwick Tree는 lowbit(x) = x & -x로 각 인덱스가 담당하는 범위를 찾는다. 배열은 1-기반 인덱싱을 사용하며, prefix sum을 구할 때는 인덱스를 줄이고 업데이트할 때는 인덱스를 늘린다. 연산이 역연산을 요구하거나 합 이외의 집계를 다뤄야 한다면 Fenwick Tree보다 Segment Tree가 맞는 경우가 많다.
질의 유형에 따라 달라지는 처리 경로
인덱싱 체계는 처음부터 고정해야 한다. Segment Tree 코드가 [0, N-1]을 사용한다면 외부 입력과 내부 연산도 그 기준을 따라야 하며, Fenwick Tree는 [1, N] 기준을 일관되게 적용해야 한다. C++에서는 합의 범위를 점검하고 64-bit 정수를 사용한다.
같은 로그 시간이라도 선택 기준은 다르다
| 지표 | Segment Tree | Fenwick Tree (BIT) |
|---|---|---|
| 성능 | 쿼리/업데이트 O(log N) | 쿼리/업데이트 O(log N) |
| 메모리 | ~4N (lazy 포함 시 증가) | ~N |
| 확장성 | 임의 모노이드, Range Assign/Add 등 자유도 높음 | 주로 합·가감 연산, 트릭으로 범위 연산 확장 가능 |
| 일관성 | 지연 전파로 구간 일관성 유지 | 프리픽스 합의 결합법칙에 의존, 단순 안정적 |
| 운영 편의 | 코드 복잡, 디버깅 난이도 존재 | 구현 간단, 유지보수 용이 |
Segment Tree는 기능 범위가 넓은 대신 메모리 사용량이 ~4N이고 코드가 복잡하다. Fenwick Tree는 메모리 사용량이 ~N이며 구현이 간결하지만, 적용 가능한 연산이 제한적이다.
집계와 카운팅에서의 적용 방식
실시간 시계열 집계에서는 API 호출 수나 에러 수의 구간 합을 구하고 1분·5분 윈도우를 분석할 수 있다. Range Add와 Range Sum을 함께 처리해야 한다면 Segment Tree가 적합하다.
온라인 랭킹이나 매칭 점수대 필터링에서는 특정 점수 구간의 사용자 수를 조회하고 가산할 수 있다. 빈도 테이블의 부분합을 처리하는 경우 Fenwick Tree를 사용할 수 있다.
광고와 과금 카운팅에서는 캠페인 구간별 임프레션 가중치를 갱신하고 집계한다. 대량 프로모션 반영에는 Lazy Propagation을 적용한 Segment Tree가 맞는다. 로그 샘플링과 필터링처럼 특정 구간을 일괄 증감한 뒤 질의하는 흐름은 두 BIT로 range add와 range sum을 구현할 수 있다.
Lazy Propagation을 적용한 Segment Tree
Python 3.10+에서 외부 패키지 없이 실행할 수 있다. 데이터 범위는 N ≤ 2e5 수준에서 실시간 처리를 권장한다.
# Python 3.10+
from typing import List
class SegmentTree:
def __init__(self, arr: List[int]):
self.n = len(arr)
size = 1
while size < self.n:
size <<= 1
self.size = size
self.tree = [0] * (2 * size)
self.lazy = [0] * (2 * size)
# build
for i, v in enumerate(arr):
self.tree[size + i] = v
for i in range(size - 1, 0, -1):
self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]
def _apply(self, idx: int, l: int, r: int, val: int):
self.tree[idx] += val * (r - l + 1)
self.lazy[idx] += val
def _push(self, idx: int, l: int, r: int):
if self.lazy[idx] != 0 and l != r:
m = (l + r) // 2
self._apply(idx << 1, l, m, self.lazy[idx])
self._apply(idx << 1 | 1, m + 1, r, self.lazy[idx])
self.lazy[idx] = 0
def range_add(self, ql: int, qr: int, val: int):
def _add(idx: int, l: int, r: int):
if qr < l or r < ql:
return
if ql <= l and r <= qr:
self._apply(idx, l, r, val)
return
self._push(idx, l, r)
m = (l + r) // 2
_add(idx << 1, l, m)
_add(idx << 1 | 1, m + 1, r)
self.tree[idx] = self.tree[idx << 1] + self.tree[idx << 1 | 1]
_add(1, 0, self.size - 1)
def range_sum(self, ql: int, qr: int) -> int:
def _sum(idx: int, l: int, r: int) -> int:
if qr < l or r < ql:
return 0
if ql <= l and r <= qr:
return self.tree[idx]
self._push(idx, l, r)
m = (l + r) // 2
return _sum(idx << 1, l, m) + _sum(idx << 1 | 1, m + 1, r)
return _sum(1, 0, self.size - 1)
# 간단 테스트
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
st = SegmentTree(arr)
assert st.range_sum(0, 4) == sum(arr)
st.range_add(1, 3, 10) # [1,12,13,14,5]
assert st.range_sum(1, 3) == 12 + 13 + 14이 구현은 0-기반 인덱싱을 사용하며 질의 범위는 [l, r]를 포함한다. 매우 큰 합(> 2^63)이 가능할 때 파이썬은 안전하지만, C++에서는 128-bit 또는 BigInt를 고려해야 한다.
Fenwick Tree로 구간 갱신과 합을 처리하기
# Python 3.10+
class Fenwick:
def __init__(self, n: int):
self.n = n
self.ft = [0] * (n + 1) # 1-based
def add(self, i: int, delta: int):
while i <= self.n:
self.ft[i] += delta
i += i & -i
def sum(self, i: int) -> int:
s = 0
while i > 0:
s += self.ft[i]
i -= i & -i
return s
class RangeFenwick:
# 지원: range_add(l, r, v), range_sum(l, r)
def __init__(self, arr):
self.n = len(arr)
self.B1 = Fenwick(self.n)
self.B2 = Fenwick(self.n)
# 초기값 반영: point add로 빌드 O(N log N)
for i, v in enumerate(arr, start=1):
self.range_add(i, i, v)
def _prefix(self, x: int) -> int:
return self.B1.sum(x) * x - self.B2.sum(x)
def range_add(self, l: int, r: int, v: int):
# 1-based inclusive
self.B1.add(l, v)
if r + 1 <= self.n:
self.B1.add(r + 1, -v)
self.B2.add(l, v * (l - 1))
if r + 1 <= self.n:
self.B2.add(r + 1, -v * r)
def range_sum(self, l: int, r: int) -> int:
return self._prefix(r) - self._prefix(l - 1)
# 간단 테스트
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
rf = RangeFenwick(arr) # 내부적으로 1-based 변환
assert rf.range_sum(1, 5) == sum(arr)
rf.range_add(2, 4, 10) # [1,12,13,14,5]
assert rf.range_sum(2, 4) == 12 + 13 + 14Fenwick Tree는 1-기반 인덱싱이 필수다. 외부에서 0-기반 입력을 받는다면 +1 변환을 일관되게 적용해야 한다. 초기화 비용은 point add 방식으로 O(N log N)이며, 누적합을 이용하면 O(N) 일괄 빌드도 가능하다.
대량 업데이트에서 얻는 변화
Lazy Propagation을 적용한 Segment Tree는 대량 Range Update가 포함된 워크로드에서 O(N)을 O(log N)으로 줄인다. N=10^6인 단일 쿼리를 기준으로 O(N)=1e6 스텝과 O(log N)≈20 스텝의 차이가 나며, 이론상 50,000배 절감이다.
Fenwick Tree는 메모리 사용량이 ~N이고 캐시 친화적으로 접근한다. 동일 하드웨어에서 랜덤 질의와 업데이트가 섞인 QPS를 높이고, 힙 사용량을 낮춰 GC와 메모리 단편화 리스크를 줄일 수 있다.
Lazy 태그 전파는 부분 업데이트 불일치를 막는다. 경계 검사와 비겹침 구간 가지치기는 지연 시간을 예측 가능한 범위로 유지하는 데도 도움이 된다.
운영 환경에서 함께 설계할 조건
Key Space가 크고 실제 사용 좌표가 제한적이라면 좌표 압축이나 희소 세그먼트 트리를 고려할 수 있다. 예를 들어 64-bit Key Space에서도 사용 중인 좌표만 노드화하면 메모리와 초기화 시간을 줄일 수 있다.
단일 트리 구조에서는 쓰기 경합이 생길 수 있다. 구간 단위 샤딩, RWLock, 배치 업데이트로 스루풋을 개선하는 방식을 검토한다. 장애 복구를 위해서는 스냅샷을 주기화하고 업데이트 스트림의 리플레이 로그를 보관하며, 재구축 시간을 줄이기 위해 델타 로그를 적용할 수 있다.
질의와 업데이트의 분포, 데이터 범위, 지연 허용치가 구조 선택의 기준이다. 복잡한 집계와 구간 업데이트가 필요하면 Segment Tree를, 합 중심의 단순한 카운팅에는 Fenwick Tree를 선택하고, 필요하면 좌표 압축과 샤딩을 함께 적용한다.