희소 테이블: 바뀌지 않는 구간 질의를 미리 준비하기
희소 테이블은 배열의 2⁰,2¹,2² 길이 구간 결과를 미리 계산해 여러 구간 질의에 사용하는 자료구조다. 원본 값이 자주 바뀌지 않는 정적 데이터에 적합하다. 최솟값 질의에서는 전처리 후 O(1) 응답이 가능하다.
최솟값처럼 중복 적용해도 결과가 같은 연산은 겹치는 블록을 사용할 수 있다.
두 작은 구간으로 큰 구간 만들기
table[k][i]를 i에서 시작하는 길이 2ᵏ 구간의 최솟값이라고 하자. 길이 2ᵏ 구간은 앞 절반과 뒤 절반으로 나뉘므로 이전 행의 두 결과 중 작은 값으로 채운다. 시작 위치마다 범위가 배열 밖으로 나가지 않아야 한다.
import math
def build_sparse_min(values):
table = [list(values)]
length = 2
while length <= len(values):
half = length // 2
previous = table[-1]
row = [min(previous[i], previous[i + half])
for i in range(len(values) - length + 1)]
table.append(row)
length *= 2
return table
def minimum(table, left, right):
# Nonempty half-open interval [left, right).
power = (right - left).bit_length() - 1
block_length = 1 << power
return min(table[power][left], table[power][right - block_length])
power는 질의 길이 이하의 가장 큰 2의 거듭제곱을 고른다. 왼쪽에서 시작한 구간과 오른쪽에서 끝나는 같은 길이 구간은 전체를 덮는다. 둘이 겹칠 수 있지만 최솟값에서는 문제가 없다. 빈 구간은 bit_length 규칙에 맞지 않아 별도로 처리해야 한다.
멱등성이 O(1) 질의를 가능하게 한다
길이 6 구간을 길이 4 구간 두 개로 덮으면 가운데 두 원소가 겹친다. min(x,x)=x이므로 같은 값을 두 번 포함해도 결과가 달라지지 않는다. 이런 성질을 멱등성이라고 한다. 최댓값, AND, OR, 최대공약수도 적합한 예다.
합은 다르다. 두 겹치는 구간 합을 더하면 중간 원소를 중복 계산한다. 일반 희소 테이블에서 겹치지 않는 2의 거듭제곱 구간으로 분해하면 O(log n) 집계가 가능하고, 합에는 누적합이 더 간단하다. 모든 결합 연산이 O(1) 질의를 얻는 것은 아니다.
전처리 시간과 공간은 O(n log n), 최솟값 질의는 O(1)이다. 원소 한 개가 바뀌면 여러 행의 많은 구간이 영향을 받아 갱신이 효율적이지 않다. 동적 데이터에는 다른 구조를 고려해야 한다.
나무의 최소 공통 조상을 오일러 순회와 깊이의 구간 최솟값 문제로 바꾸는 응용도 있다. 이 경우도 변환의 의미와 질의 조건을 별도로 확인한다.
희소 테이블은 큰 전처리 비용을 많은 읽기 질의에 나누어 쓰는 선택이다. 데이터가 고정적인지, 집계 연산이 멱등적인지, 충분한 메모리가 있는지 확인하면 왜 빠른지와 언제 부적합한지 함께 이해할 수 있다.