[Daily morning study] 스파스 테이블(Sparse Table)과 구간 최솟값 쿼리(RMQ)
#daily morning study
스파스 테이블이란?
스파스 테이블(Sparse Table)은 정적 배열에서 구간 쿼리(Range Query)를 O(1)에 처리하기 위한 자료구조다. 대표적으로 구간 최솟값 쿼리(RMQ, Range Minimum Query) 에 사용된다.
- 전처리(build): O(n log n) 시간, O(n log n) 공간
- 쿼리: O(1) (겹치는 구간 허용 쿼리의 경우)
세그먼트 트리가 업데이트를 지원하는 범용 자료구조라면, 스파스 테이블은 배열이 변하지 않는 상황에서 쿼리 속도를 극한으로 끌어올린 특화된 도구다.
핵심 아이디어: 2의 거듭제곱 구간
스파스 테이블은 2의 거듭제곱 길이의 구간에 대한 정보를 미리 계산해 저장한다.
sparse[i][j] = arr[i..i + 2^j - 1] 구간의 최솟값
| j (구간 길이 2^j) | 의미 |
|---|---|
| j = 0 | 길이 1짜리 구간, 즉 arr[i] 자체 |
| j = 1 | 길이 2짜리 구간 |
| j = 2 | 길이 4짜리 구간 |
| j = k | 길이 2^k짜리 구간 |
점화식:
sparse[i][j] = min(sparse[i][j-1], sparse[i + 2^(j-1)][j-1])
길이 2^j 구간은 길이 2^(j-1) 짜리 두 구간으로 나뉜다. 왼쪽 절반 [i, i + 2^(j-1) - 1], 오른쪽 절반 [i + 2^(j-1), i + 2^j - 1]의 최솟값을 비교한다.
전처리 (Build)
import math
def build(arr):
n = len(arr)
LOG = math.floor(math.log2(n)) + 1 if n > 0 else 1
sparse = [[float('inf')] * LOG for _ in range(n)]
# j = 0: 길이 1 구간은 자기 자신
for i in range(n):
sparse[i][0] = arr[i]
# j >= 1: 2의 거듭제곱 구간 채우기
for j in range(1, LOG):
for i in range(n - (1 << j) + 1):
sparse[i][j] = min(sparse[i][j-1], sparse[i + (1 << (j-1))][j-1])
return sparse, LOG
쿼리 (Query) — O(1)
구간 [l, r]의 최솟값을 구하는 방법:
- 구간 길이
len = r - l + 1을 구한다. k = floor(log2(len))을 구한다.[l, l + 2^k - 1]과[r - 2^k + 1, r]두 구간은[l, r]을 완전히 덮는다.- 두 구간이 겹쳐도 최솟값(min)은 중복을 허용하므로 결과가 올바르다.
def query(sparse, l, r):
length = r - l + 1
k = math.floor(math.log2(length))
return min(sparse[l][k], sparse[r - (1 << k) + 1][k])
겹치는 두 구간의 최솟값을 비교하므로 중복 원소를 세도 답이 바뀌지 않는다. 이 성질을 멱등성(idempotency) 이라 하고, 이 덕분에 O(1) 쿼리가 가능하다.
합(sum)은 중복을 허용하면 답이 달라지므로 스파스 테이블로 O(1) 쿼리가 불가능하다. 대신 세그먼트 트리나 펜윅 트리를 쓴다.
전체 예시
import math
def build(arr):
n = len(arr)
LOG = max(1, math.floor(math.log2(n)) + 1)
sparse = [[float('inf')] * LOG for _ in range(n)]
for i in range(n):
sparse[i][0] = arr[i]
for j in range(1, LOG):
for i in range(n - (1 << j) + 1):
sparse[i][j] = min(sparse[i][j-1], sparse[i + (1 << (j-1))][j-1])
return sparse, LOG
def query(sparse, l, r):
k = math.floor(math.log2(r - l + 1))
return min(sparse[l][k], sparse[r - (1 << k) + 1][k])
arr = [2, 4, 3, 1, 6, 7, 8, 9, 1, 7]
sparse, LOG = build(arr)
print(query(sparse, 0, 4)) # min(2,4,3,1,6) = 1
print(query(sparse, 2, 7)) # min(3,1,6,7,8,9) = 1
print(query(sparse, 5, 9)) # min(7,8,9,1,7) = 1
시간 / 공간 복잡도
| 단계 | 복잡도 |
|---|---|
| 전처리 (Build) | O(n log n) |
| 쿼리 (Query) | O(1) |
| 공간 | O(n log n) |
세그먼트 트리와 비교
| 항목 | 스파스 테이블 | 세그먼트 트리 |
|---|---|---|
| 전처리 | O(n log n) | O(n) |
| 쿼리 | O(1) | O(log n) |
| 업데이트 | 불가 | O(log n) |
| 공간 | O(n log n) | O(n) |
| 멱등 연산 | min, max, gcd 등 | 모든 연산 |
배열이 고정된 상태에서 쿼리를 수백만 번 반복해야 한다면 스파스 테이블이 훨씬 빠르다. 반대로 배열 원소가 자주 바뀐다면 세그먼트 트리를 써야 한다.
활용 사례
LCA (Lowest Common Ancestor)
트리에서 두 노드의 최소 공통 조상을 구할 때, Euler Tour + 스파스 테이블 조합으로 O(n log n) 전처리 후 O(1) LCA 쿼리가 가능하다.
구간 GCD
gcd(a, gcd(a, b)) = gcd(a, b) 성질(멱등성)이 있어 스파스 테이블로 구간 GCD를 O(1)에 구할 수 있다.
슬라이딩 윈도우 최솟값
덱(Deque)으로도 가능하지만, 스파스 테이블이 있으면 O(1) 쿼리로 더 단순하게 처리할 수 있다.
구현 시 주의점
log2계산은 매번 하면 느릴 수 있으니 log 테이블을 미리 계산해두면 쿼리가 더 빠르다.
# log 테이블 전처리
log_table = [0] * (n + 1)
for i in range(2, n + 1):
log_table[i] = log_table[i // 2] + 1
- 배열 크기 n이 1일 때
log2(1) = 0이므로 LOG를 최소 1로 설정해야 한다. - C++에서는
__builtin_clz비트 연산으로 더 빠르게 log를 계산할 수 있다.
int k = 31 - __builtin_clz(r - l + 1);
return min(sparse[l][k], sparse[r - (1 << k) + 1][k]);
