희소 테이블 (Sparse Table)

지난 글에서 다차원 공간 탐색을 위한 k-d 트리를 다뤘습니다. 이번에는 정적 배열에서 구간 최솟값(Range Minimum Query, RMQ) 쿼리를 놀라운 O(1)로 처리하는 희소 테이블(Sparse Table)을 알아봅니다.

핵심 아이디어

길이 2ʲ인 부분 배열의 최솟값을 미리 계산해 저장해 두면, 임의 구간 [l, r]에 대해 두 개의 미리 계산된 구간으로 덮을 수 있습니다. min은 멱등(idempotent) 연산이라 겹치는 원소를 두 번 세어도 결과가 변하지 않기 때문입니다.

k = floor(log₂(r - l + 1))
RMQ(l, r) = min(sp[k][l], sp[k][r - 2ᵏ + 1])

두 구간이 겹쳐도 최솟값이 올바르게 나옵니다. 이게 O(1) 쿼리의 비밀입니다.

전처리

const LOG = [0, 0];
for (let i = 2; i <= n; i++)
  LOG[i] = LOG[i >> 1] + 1;

// sp[j][i] = min(a[i..i + 2^j - 1])
const sp = Array.from({ length: LOG[n] + 1 }, () => new Array(n));
for (let i = 0; i < n; i++) sp[0][i] = a[i];

for (let j = 1; (1 << j) <= n; j++) {
  for (let i = 0; i + (1 << j) <= n; i++) {
    sp[j][i] = Math.min(
      sp[j - 1][i],
      sp[j - 1][i + (1 << (j - 1))]
    );
  }
}

점화식: sp[j][i] = min(sp[j-1][i], sp[j-1][i + 2^(j-1)])
→ “2ʲ 길이 구간의 최솟값 = 앞쪽 절반과 뒤쪽 절반의 최솟값 중 작은 것”

O(1) 쿼리

function query(l, r) {
  const k = LOG[r - l + 1];
  return Math.min(sp[k][l], sp[k][r - (1 << k) + 1]);
}

LOG[len] 조회로 k를 O(1)에 구하고, 두 번의 배열 접근으로 끝납니다.

멱등 연산만 O(1) 가능

연산	O(1) 가능?	이유
min, max	✓	멱등: 중복 원소를 두 번 봐도 무관
gcd, and, or	✓	멱등
sum	✗	겹치는 구간을 두 번 더하면 오류

합산 쿼리가 필요하면 펜윅 트리나 세그먼트 트리를 써야 합니다.

LCA 응용

희소 테이블의 가장 유명한 활용처는 LCA(Lowest Common Ancestor) 입니다.

1. 오일러 투어: DFS로 트리를 배열로 변환 (방문할 때마다 깊이 기록)
2. LCA(u, v) = 오일러 투어 배열에서 u와 v 사이 구간의 최소 깊이 노드
3. 해당 RMQ를 희소 테이블로 O(1) 처리

# 오일러 투어로 LCA
# euler[]: DFS 방문 순서, first[v]: 노드 v의 첫 방문 위치
def lca(u, v):
    l, r = min(first[u], first[v]), max(first[u], first[v])
    return euler[rmq(l, r)]  # rmq: 깊이가 최소인 인덱스

복잡도

	시간	공간
전처리	O(n log n)	O(n log n)
쿼리	O(1)	—

한계

• 배열이 정적이어야 합니다 (값 업데이트 불가). 동적이면 세그먼트 트리 사용
• 메모리가 O(n log n)으로 n이 크면 주의 (n=10⁷이면 약 23×10⁷ ≈ 920MB)

---

지난 글: k-d 트리

다음 글: 그래프 표현

읽어주셔서 감사합니다. 😊