구간 트리 안내서 · 4/6
이 장에서는 구간 트리의 시간과 공간 복잡도를 분석하고, 같은 문제를 푸는 다른 자료 구조와 비교합니다. 어떤 상황에서 무엇을 고를지 판단하는 기준을 잡는 것이 목표입니다.
| 연산 | 재귀 구간 트리 | 반복문 구간 트리 | 비고 |
|---|---|---|---|
| 만들기 | O(n) | O(n) | 노드마다 합치기 한 번 |
| 점 갱신 | O(log n) | O(log n) | 리프에서 루트까지 한 경로 |
| 구간 질의 | O(log n) | O(log n) | 층마다 많아야 노드 2개를 결과에 넣음 |
| 구간 갱신(지연 전파) | O(log n) | 구현이 복잡 | 보통 재귀로 구현 |
구간 트리에서는 최선 · 평균 · 최악이 크게 다르지 않습니다. 길이 1인 질의도 리프까지 내려가야 하고, 전체 구간 질의는 루트에서 바로 끝나므로 상수가 조금 다를 뿐 모두 O(log n) 안에 들어갑니다.
재귀 질의에서 "일부만 겹치는" 노드는 질의 구간의 왼쪽 끝이나 오른쪽 끝을 품은 노드뿐입니다. 한 층에서 끝점을 품을 수 있는 노드는 많아야 두 개이므로, 층마다 많아야 네 개의 노드를 방문합니다. 층이 약 log2 n개이므로 전체 방문 수는 4 log2 n 정도로 제한됩니다. 직접 세어 보면 확인할 수 있습니다.
import math
import random
n = 1 << 16
tree = [1] * (4 * n) # 값은 상관없고 방문 횟수만 센다
visits = 0
def query(node, lo, hi, l, r):
global visits
visits += 1
if r <= lo or hi <= l:
return 0
if l <= lo and hi <= r:
return tree[node]
mid = (lo + hi) // 2
return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid, hi, l, r)
worst = 0
for _ in range(2000):
l = random.randrange(n)
r = random.randrange(l + 1, n + 1)
visits = 0
query(1, 0, n, l, r)
worst = max(worst, visits)
print(worst, 4 * math.log2(n)) # 예: 63 64.02n - 1개지만, 1부터 번호를 매기면 n이 2의 거듭제곱이 아닐 때 번호가 2n을 넘을 수 있습니다. 그래서 흔히 4n 칸을 잡습니다. 정확히는 2 * 2^ceil(log2 n) 칸이면 충분합니다.2n 칸입니다.n + 1 칸입니다.import math
def recursive_size(n):
return 2 * (1 << math.ceil(math.log2(n))) if n > 1 else 2
for n in [8, 9, 1000, 100_000]:
print(n, recursive_size(n), 4 * n, 2 * n, n + 1)
# 8 16 32 16 9
# 9 32 36 18 10
# 1000 2048 4000 2000 1001
# 100000 262144 400000 200000 100001| 방법 | 만들기 | 점 갱신 | 구간 질의 | 구간 갱신 | 추가 메모리 | 지원 연산 |
|---|---|---|---|---|---|---|
| 배열 그대로 | - | O(1) | O(n) | O(n) | 없음 | 무엇이든 |
| 누적 합 | O(n) | O(n) | O(1) | O(n) | n + 1 | 되돌릴 수 있는 연산(합, XOR) |
| 희소 테이블 | O(n log n) | 불가 | O(1) | 불가 | n log n | 겹쳐도 되는 연산(최솟값, 최댓값, GCD) |
| 제곱근 분할 | O(n) | O(1) | O(sqrt n) | O(sqrt n) | sqrt n | 대부분 |
| 펜윅 트리 | O(n) | O(log n) | O(log n) | 변형으로 가능 | n + 1 | 합처럼 되돌릴 수 있는 연산 |
| 구간 트리 | O(n) | O(log n) | O(log n) | 지연 전파로 O(log n) | 2n~4n | 결합 법칙을 만족하는 연산 |
펜윅 트리는 점근 복잡도가 구간 트리와 같지만, 코드가 짧고 메모리를 절반 이하로 쓰며 실제 실행도 빠른 편입니다. 반면 최솟값 · 최댓값 질의나 복잡한 구간 갱신에는 구간 트리가 더 유연합니다.
Python에서 n = 200,000, 요청 200,000개 정도면 반복문 구간 트리는 컴퓨터에 따라 몇 초 안에 끝납니다. 같은 일을 배열 그대로 하면 질의마다 평균 수만 번의 덧셈, 모두 합쳐 백억 번 넘는 덧셈이 필요해 사실상 끝나지 않습니다. 다음 코드로 직접 비교해 볼 수 있습니다.
import random
import time
n, q = 200_000, 200_000
a = [random.randint(1, 100) for _ in range(n)]
tree = [0] * n + a
for i in range(n - 1, 0, -1):
tree[i] = tree[2 * i] + tree[2 * i + 1]
start = time.perf_counter()
for _ in range(q):
l = random.randrange(n)
r = random.randrange(l + 1, n + 1)
lo, hi, total = l + n, r + n, 0
while lo < hi:
if lo & 1:
total += tree[lo]; lo += 1
if hi & 1:
hi -= 1; total += tree[hi]
lo //= 2; hi //= 2
print(f"{time.perf_counter() - start:.2f}s")구간 트리는 만들기 O(n), 점 갱신과 구간 질의 O(log n), 메모리 2n~4n입니다. 값이 바뀌지 않으면 누적 합이나 희소 테이블, 합만 필요하면 펜윅 트리, 최솟값 · 최댓값이나 구간 갱신까지 필요하면 구간 트리를 고르는 것이 일반적인 기준입니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.