에듀테크 프로젝트 대시보드
스파스 테이블 (Sparse Table)
배열이 절대 안 바뀐다면 — 구간 최솟값 질의를 O(1)에 끝내는 정적 전처리 구조
"구간 [l, r]의 최솟값은?" 같은 질의를 아주 많이 던져야 한다고 하자.
매번 min(arr[l:r+1])처럼 스캔하면 한 번에 O(r-l)이라, 질의가 수십만 번이면 감당이 안 된다.
그런데 배열 값이 중간에 절대 바뀌지 않는다는 조건이 붙으면 얘기가 달라진다 — 모든 질의에서
쓰일 법한 답을 미리 다 계산해 두면 되기 때문이다.
스파스 테이블은 구간 길이를 2의 거듭제곱(1, 2, 4, 8, …)으로만 한정해서 그 값들을 몽땅 표로
저장해 둔다. 임의의 [l, r]은 정확히 안 나눠도 2의 거듭제곱 구간 두 개로
덮을 수 있어서, 전처리에 O(n log n)을 쓰는 대신 질의는 O(1)에 끝난다. 세그먼트 트리·펜윅 트리보다
앞서 배우는 이유는 딱 하나 — 갱신이 없다는 가정 덕분에 구조가 훨씬 단순하기 때문이다.
dp[0][i] = arr[i] (길이 1)에서 시작해서, 한 층 위로 올라갈 때마다
바로 아래 층의 칸 두 개를 합쳐서 만든다:
dp[j][i] = min( dp[j-1][i], dp[j-1][i + 2^(j-1)] )
길이 2ʲ짜리 구간은 길이 2ʲ⁻¹짜리 구간 두 개를 반으로 딱 붙인 것이므로,
그 두 구간의 최솟값 중 더 작은 쪽이 곧 전체의 최솟값이다. 층은 log₂n개, 각 층마다
최대 n칸이므로 전처리는 시간·공간 모두 O(n log n).
맨 아래 배열 칸을 클릭하면 값이 1씩 바뀐다(9 다음은 0). 슬라이더로 배열 크기를 바꾸고 배열 랜덤 생성을 누르면 새 배열이 만들어진다. 테이블 만들기를 누르면 j=0(원본)부터 한 층씩, 각 칸이 왼쪽 소스와 오른쪽 소스 두 칸에서 어떻게 합쳐지는지 연결선으로 보여준다.
임의의 [l, r]을 딱 맞게 자를 필요가 없다. 길이 2ᵏ ≤ (r-l+1)인
가장 큰 k를 골라 [l, l+2ᵏ-1]과 [r-2ᵏ+1, r] 두 블록으로
덮으면 끝. 두 블록이 겹칠 수도 있는데, min은 같은 원소를 두 번 봐도 답이 변하지 않는다 —
이런 성질을 멱등(idempotent)이라고 부른다. max, gcd도 마찬가지다.
슬라이더로 [l, r]을 고르면 블록 A와
블록 B가 배열 위에 표시되고, 겹치는 칸은
세 번째 색으로 보인다. 쿼리 실행을 누르면 위쪽 dp 표에서
실제로 참조하는 두 칸도 함께 반짝인다 — 이 두 칸만 보면 끝이라 O(1)이다.
# 전처리: O(n log n) n = len(arr) LOG = n.bit_length() # 2^LOG-1 >= n dp = [[0]*n for _ in range(LOG)] dp[0] = arr[:] # j=0: 길이 1 구간 = 원소 자신 for j in range(1, LOG): half = 1 << (j - 1) # 2^(j-1) for i in range(n - (1 << j) + 1): # 길이 2^j가 안 벗어나는 i까지 dp[j][i] = min(dp[j-1][i], dp[j-1][i + half]) # 쿼리: O(1), 겹치는 두 블록으로 덮기 def query(l, r): k = (r - l + 1).bit_length() - 1 # 2^k <= r-l+1 인 최대 k return min(dp[k][l], dp[k][r - (1 << k) + 1])
| 항목 | 스파스 테이블 | 세그먼트 트리 | 펜윅 트리 |
|---|---|---|---|
| 전처리 | O(n log n) | O(n) | O(n) |
| 구간 쿼리 | O(1) | O(log n) | O(log n) · query(r)-query(l-1) |
| 값 갱신 | 불가 (정적 배열 전용) | O(log n) | O(log n) |
| 지원 연산 | min / max / gcd 등 멱등 연산만 | 결합법칙만 성립하면 무엇이든(합 포함) | 합·XOR 등 역원 있는 연산 |
| 메모리 | O(n log n) | O(n) ~ O(4n) | O(n) |
| 구현 난이도 | 가장 쉬움 | 중간 | 가장 짧음 |
배열이 고정되어 있고 구간 최솟값·최댓값·GCD 같은 멱등 연산 질의만 반복된다면 스파스 테이블이 가장 간단하고 빠르다(구현도 짧고 쿼리는 상수 시간). 반대로 값이 계속 바뀌거나 구간 합이 필요하면 세그먼트 트리나 펜윅 트리로 넘어가야 한다. 실전에서는 "LCA를 위한 오일러 투어 + RMQ" 조합에서 스파스 테이블이 아주 자주 쓰인다.