희소 테이블은 배열이 바뀌지 않을 때 구간 질의를 빠르게 처리하기 위한 자료구조입니다. 세그먼트 트리처럼 구간을 다루지만, 업데이트를 포기하는 대신 질의를 더 단순하게 만들 수 있습니다.
핵심은 배열이 고정되어 있고 구간 최솟값 같은 질의가 많다면 희소 테이블이 세그먼트 트리보다 편할 수 있다는 점입니다.
희소 테이블은 무엇을 미리 저장할까
그림의 질의 [1,5]는 길이 5입니다. 가장 큰 2의 거듭제곱 길이 4를 잡고, 왼쪽에서 시작하는 구간과 오른쪽에서 끝나는 구간 두 개를 비교하면 됩니다.
희소 테이블은 길이 1, 2, 4, 8처럼 2의 거듭제곱 길이 구간의 답을 미리 저장합니다. 예를 들어 table[k][i]는 i에서 시작하는 길이 2^k 구간의 최솟값을 의미할 수 있습니다.
이렇게 저장해 두면 큰 구간도 두 개의 2의 거듭제곱 구간으로 덮어 빠르게 답할 수 있습니다.
세그먼트 트리와 가장 큰 차이
이 비교표를 기준으로 보면 선택이 단순해집니다. 배열이 바뀌지 않고 RMQ가 많으면 희소 테이블, 값이 계속 바뀌면 세그먼트 트리를 고르는 식입니다.
세그먼트 트리는 업데이트와 질의를 모두 처리하기 좋습니다. 반면 희소 테이블은 업데이트가 거의 불가능하다고 보는 편이 안전합니다.
대신 배열이 고정되어 있다면 전처리 후 구간 최솟값 질의를 O(1)에 답할 수 있습니다. 그래서 정적 RMQ에서는 구현과 성능이 모두 매력적입니다.
왜 RMQ는 두 구간이 겹쳐도 괜찮을까
구간 최솟값은 같은 원소가 두 번 들어가도 결과가 바뀌지 않습니다. 예를 들어 min(3, 3)은 여전히 3입니다. 이런 성질을 idempotent라고 부릅니다.
그래서 길이 L인 구간을 덮는 두 개의 2의 거듭제곱 구간이 조금 겹쳐도, min/max/gcd 같은 연산은 답이 망가지지 않습니다.
Python 구현
import math
class SparseTable:
def __init__(self, arr):
self.n = len(arr)
self.log = [0] * (self.n + 1)
for i in range(2, self.n + 1):
self.log[i] = self.log[i // 2] + 1
k = self.log[self.n] + 1
self.table = [arr[:]]
for level in range(1, k):
length = 1 << level
half = length >> 1
prev = self.table[level - 1]
row = []
for i in range(self.n - length + 1):
row.append(min(prev[i], prev[i + half]))
self.table.append(row)
def range_min(self, left, right):
length = right - left + 1
k = self.log[length]
return min(
self.table[k][left],
self.table[k][right - (1 << k) + 1],
)이 코드는 구간 최솟값을 기준으로 했습니다. range_min(left, right)는 닫힌 구간 [left, right]의 최솟값을 반환합니다.
언제 세그먼트 트리를 써야 할까
- 배열 값이 중간에 바뀐다.
- 구간 합처럼 겹치면 안 되는 연산을 단순하게 처리하고 싶다.
- lazy propagation 같은 구간 업데이트가 필요하다.
- 온라인으로 업데이트와 질의가 섞여 들어온다.
반대로 업데이트가 없고 RMQ가 많다면 희소 테이블이 좋은 선택입니다. 기본 개념과 수식은 cp-algorithms Sparse Table 문서에서도 확인할 수 있습니다.
상태를 미리 압축해 두고 빠르게 꺼내 쓰는 감각은 비트마스크 DP 글과도 연결됩니다. 둘 다 전처리나 상태 표현을 통해 반복 계산을 줄인다는 공통점이 있습니다.
정리
희소 테이블은 세그먼트 트리보다 강한 자료구조가 아닙니다. 업데이트를 포기하고 정적 구간 질의에 집중한 도구입니다. 문제에서 배열이 변하지 않고 구간 최솟값을 많이 묻는다면 먼저 떠올려볼 만합니다.
