희소 배열 (Sparse Table)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 2분 · 726자/단어 #algorithm #data-structure #sparse-table #rmq

정의

희소 배열 (Sparse Table) 은 정적 배열에서 결합 법칙을 만족하는 idempotent 연산 (min, max, gcd, lcm 등) 의 구간 쿼리를 O(1) 시간에 처리하는 자료구조. 전처리 O(N log N), 공간 O(N log N).

idempotent: f(a, a) = a 인 성질 (min, max, gcd 는 만족, sum 은 불만족).

문제 상황과 동기

길이 N 배열에서 RMQ (Range Minimum Query) min(a[l..r]) 을 Q 번 물을 때:

naive: 매 쿼리마다 O(r - l + 1) = O(N). Q 개면 O(N · Q).
세그먼트 트리: O(N log N) 전처리, O(log N) 쿼리. 갱신도 O(log N).
희소 배열: 갱신 없이 쿼리만 있으면 O(1) 에 답 가능. 전처리 O(N log N).

핵심 통찰: 모든 구간 [l, r] 은 두 개의 2^k 길이 블록 으로 덮을 수 있음. idempotent 성질 덕분에 중복 허용.

실무: 로그 분석, 센서 데이터 이상치 탐지 등 대량 읽기 / 갱신 없음.

시각화

핵심 아이디어

테이블 st[i][j] = [i, i + 2^j - 1] 구간의 min (또는 max / gcd).

st[i][0] = a[i]                               (길이 1)
st[i][j] = f(st[i][j-1], st[i + 2^(j-1)][j-1])  (두 반쪽 merge)

쿼리 [l, r] 시:

k = floor(log2(r - l + 1))
answer = f(st[l][k], st[r - 2^k + 1][k])

두 블록이 겹쳐도 idempotent 때문에 min / max / gcd 결과는 동일.

알고리즘

preprocess(a, N):
    K = floor(log2(N)) + 1
    for i in 0..N-1:
        st[i][0] = a[i]
    for j in 1..K:
        for i in 0..(N - 2^j):
            st[i][j] = f(st[i][j-1], st[i + 2^(j-1)][j-1])

query(l, r):
    k = floor(log2(r - l + 1))
    return f(st[l][k], st[r - 2^k + 1][k])

구현

// Sparse Table for RMQ, O(N log N) build + O(1) query
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q; cin >> n >> q;
  vector<int> a(n);
  for (auto& v : a) cin >> v;

  int K = __lg(n) + 1;
  vector<vector<int>> st(n, vector<int>(K));
  for (int i = 0; i < n; i++) st[i][0] = a[i];
  for (int j = 1; j < K; j++) {
      for (int i = 0; i + (1 << j) <= n; i++)
          st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
  }

  while (q--) {
      int l, r; cin >> l >> r; l--; r--;  // 0-indexed [l, r]
      int k = __lg(r - l + 1);
      cout << min(st[l][k], st[r - (1 << k) + 1][k]) << "\n";
  }
}

# Sparse Table for RMQ, bit_length 으로 log2
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))

K = n.bit_length()
st = [[0] * K for _ in range(n)]
for i in range(n):
  st[i][0] = a[i]

for j in range(1, K):
  i = 0
  while i + (1 << j) <= n:
      st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])
      i += 1

out = []
for _ in range(q):
  l, r = map(int, input().split())
  l -= 1; r -= 1  # 0-indexed [l, r]
  k = (r - l + 1).bit_length() - 1
  out.append(str(min(st[l][k], st[r - (1 << k) + 1][k])))
print("\n".join(out))

// Sparse Table for RMQ, 2D 배열 동적 할당 주의
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int q = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++)
          a[i] = Integer.parseInt(st.nextToken());

      int K = 32 - Integer.numberOfLeadingZeros(n);
      int[][] sparse = new int[n][K];
      for (int i = 0; i < n; i++) sparse[i][0] = a[i];
      for (int j = 1; j < K; j++) {
          for (int i = 0; i + (1 << j) <= n; i++)
              sparse[i][j] = Math.min(sparse[i][j-1], sparse[i + (1 << (j-1))][j-1]);
      }

      StringBuilder sb = new StringBuilder();
      for (int qq = 0; qq < q; qq++) {
          st = new StringTokenizer(br.readLine());
          int l = Integer.parseInt(st.nextToken()) - 1;
          int r = Integer.parseInt(st.nextToken()) - 1;
          int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
          int ans = Math.min(sparse[l][k], sparse[r - (1 << k) + 1][k]);
          sb.append(ans).append('\n');
      }
      System.out.print(sb);
  }
}

stdin

결과

1
1
1

복잡도

항목	값
전처리 시간	O(N log N)
전처리 공간	O(N log N)
쿼리 시간	O(1)
갱신	불가 (정적)
적용 연산	idempotent + 결합법칙 (min, max, gcd, lcm)

변형 / 활용

1. max query

min 을 max 로 바꾸면 RMaxQ.

2. gcd query

f(x, y) = gcd(x, y) 도 idempotent. st[i][j] = gcd(st[i][j-1], st[i + 2^(j-1)][j-1]).

3. LCA (Lowest Common Ancestor)

트리를 Euler tour + depth 배열로 변환하면 LCA 를 RMQ 로. O(N log N) 전처리, O(1) LCA.

4. 2D Sparse Table

2D 배열 st[i][j][ki][kj] 로 확장 가능. 전처리 O(N M log N log M), 쿼리 O(1).

함정

1. sum / xor 은 불가

idempotent 하지 않으면 중복 영역 두 번 계산. sum 은 누적 합 또는 세그먼트 트리.

2. log2 계산

C++ __lg(x) = floor(log2(x)). Python x.bit_length() - 1. Java 31 - Integer.numberOfLeadingZeros(x).

3. 메모리

N=10^5, K=17 이면 N × K ≈ 1.7M 배열. N=10^6 면 17M, 정수 4B 기준 68MB. 큰 N 주의.

4. 1-indexed vs 0-indexed

쿼리 입력 1-indexed 면 l--, r-- 필수.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 17435	합성함수와 쿼리	-	kokoa-lab
BOJ 3117	YouTube	-	kokoa-lab
BOJ 11440	피보나치 수의 제곱의 합	-	kokoa-lab

참고

세그먼트 트리 (갱신 필요할 때)
누적 합 (sum 쿼리)
최소 공통 조상

이 글의 용어 (3개)

누적 합 (Prefix Sum)algorithm: 정의 누적 합 (Prefix Sum) 은 배열 에 대해 (또는 1-indexed ) 을 미리 계산해 두고, 임의 구간 합 을 O(1) 에 구하는 정형. 문제 풀이에서 "구간 N …
세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
최소 공통 조상 (Lowest Common Ancestor)algorithm: 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…