복잡도

이 장에서는 구간 트리의 시간과 공간 복잡도를 분석하고, 같은 문제를 푸는 다른 자료 구조와 비교합니다. 어떤 상황에서 무엇을 고를지 판단하는 기준을 잡는 것이 목표입니다.

시간 복잡도

구간 트리에서는 최선 · 평균 · 최악이 크게 다르지 않습니다. 길이 1인 질의도 리프까지 내려가야 하고, 전체 구간 질의는 루트에서 바로 끝나므로 상수가 조금 다를 뿐 모두 O(log n) 안에 들어갑니다.

질의가 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.0

공간 복잡도

• 재귀 구간 트리: 노드는 2n - 1개지만, 1부터 번호를 매기면 n이 2의 거듭제곱이 아닐 때 번호가 2n을 넘을 수 있습니다. 그래서 흔히 4n 칸을 잡습니다. 정확히는 2 * 2^ceil(log2 n) 칸이면 충분합니다.
• 반복문 구간 트리: 정확히 2n 칸입니다.
• 지연 전파: lazy 배열이 같은 크기로 하나 더 필요합니다.
• 펜윅 트리: 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

다른 방법과 비교

펜윅 트리는 점근 복잡도가 구간 트리와 같지만, 코드가 짧고 메모리를 절반 이하로 쓰며 실제 실행도 빠른 편입니다. 반면 최솟값 · 최댓값 질의나 복잡한 구간 갱신에는 구간 트리가 더 유연합니다.

실제 실행 시간 감각

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입니다. 값이 바뀌지 않으면 누적 합이나 희소 테이블, 합만 필요하면 펜윅 트리, 최솟값 · 최댓값이나 구간 갱신까지 필요하면 구간 트리를 고르는 것이 일반적인 기준입니다.