희소 테이블은 배열 값이 바뀌지 않는 상황에서 구간 질의를 빠르게 처리하는 자료구조입니다. 특히 구간 최소값(RMQ)처럼 같은 원소를 두 번 봐도 답이 깨지지 않는 연산에서 강합니다.
이 글에서는 희소 테이블을 단순 정의로 끝내지 않고, 왜 세그먼트 트리보다 단순하게 느껴지는지, 어떤 문제 신호를 보면 떠올려야 하는지, 실제 코드에서는 어떤 테이블을 채우는지까지 단계적으로 설명하겠습니다. 비교 기준이 먼저 필요하다면 펜윅 트리 vs 세그먼트 트리 글도 함께 보면 좋습니다.
희소 테이블을 한 문장으로 말하면
희소 테이블은 길이가 1, 2, 4, 8처럼 2의 거듭제곱 길이 구간의 답을 미리 계산해 두고, 나중 질의는 그 조각들을 꺼내 조합해서 처리하는 구조입니다.
특히 RMQ에서는 구간을 여러 조각으로 나누지 않아도 됩니다. 길이가 같은 두 개의 겹치는 구간으로 덮을 수 있고, 최소값은 중복을 허용하므로 답이 유지됩니다.
왜 하필 2의 거듭제곱 구간일까
길이 2k 구간은 정확히 길이 2k-1 구간 두 개로 나뉩니다. 그래서 점화식이 아주 깔끔합니다. 더 작은 답 두 개만 있으면 더 큰 구간의 답을 만들 수 있습니다.
- st[0][i] = 길이 1 구간의 답
- st[1][i] = 길이 2 구간의 답
- st[2][i] = 길이 4 구간의 답
- st[k][i] = 시작점 i, 길이 2^k 구간의 답
즉 희소 테이블은 모든 구간을 다 저장하는 구조가 아니라, 나중에 필요한 구간을 재조합할 수 있을 정도로만 저장하는 구조입니다.
작은 예제로 테이블 감각 잡기
배열이 [7, 2, 3, 0, 5, 10, 3, 12, 18] 라고 해보겠습니다. 길이 1은 원본 값이고, 길이 2는 인접 두 칸의 최소, 길이 4는 길이 2 두 구간의 최소를 다시 비교해 얻습니다.
예를 들어 시작점 0의 길이 4 구간은 [7,2,3,0] 입니다. 이 구간은 [7,2] 와 [3,0] 으로 나뉘므로 답은 min(2, 0) = 0 이 됩니다.
RMQ 질의가 왜 O(1) 이 될까
질의 구간 길이를 len = R - L + 1 라고 하면, 그 이하인 가장 큰 2의 거듭제곱 길이를 2^k 로 잡을 수 있습니다. 그러면 답은 min(st[k][L], st[k][R - 2^k + 1]) 입니다.
여기서 중요한 포인트는 두 구간이 겹쳐도 괜찮다는 점입니다. 최소값은 같은 원소를 두 번 포함해도 결과가 달라지지 않기 때문입니다. 그래서 여러 조각을 순회할 필요 없이 두 번의 lookup만으로 끝납니다.
왜 구간 합은 같은 방식으로 안 될까
합은 중복에 민감합니다. 같은 원소를 두 번 더하면 답이 커져 버립니다. 그래서 희소 테이블이 RMQ에서 O(1) 인 이유를 구간 합에도 그대로 가져오면 안 됩니다.
실전에서는 이렇게 기억하면 충분합니다. 최소값·최댓값처럼 중복 허용 연산은 희소 테이블과 궁합이 좋고, 합처럼 중복이 깨지는 연산은 같은 방식의 O(1) 질의를 기대하면 안 된다고 보면 됩니다. 이 핵심은 cp-algorithms Sparse Table 문서에서도 같은 방향으로 설명합니다.
세그먼트 트리와 언제 갈릴까
- 업데이트가 있으면 세그먼트 트리가 더 자연스럽습니다.
- 업데이트가 없고 질의가 많으면 희소 테이블이 더 매력적일 수 있습니다.
- 희소 테이블은 전처리와 메모리를 더 쓰는 대신 RMQ 질의를 O(1) 로 줄입니다.
- 세그먼트 트리는 구현 범용성이 높고, 희소 테이블은 정적 문제에서 특히 강합니다.
즉 둘의 차이는 누가 더 고급인가가 아닙니다. 문제에 업데이트가 있느냐 없느냐가 가장 큰 갈림길입니다.
문제에서 어떤 신호를 보면 희소 테이블을 떠올릴까
- 배열은 고정되어 있고 값 변경 쿼리가 없다
- 구간 최소값, 최대값, gcd 질의가 반복된다
- 질의 수가 매우 많다
- 전처리를 해두고 온라인 질의를 빠르게 처리해야 한다
반대로 update 쿼리가 함께 나오거나, lazy propagation 같은 표현이 필요해 보이면 희소 테이블보다 세그먼트 트리 쪽일 가능성이 큽니다.
C++ 구현 예시
#include
using namespace std;
struct SparseTable {
vector<vector> st;
vector lg;
SparseTable(const vector& a) {
int n = (int)a.size();
lg.assign(n + 1, 0);
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
int K = lg[n];
st.assign(K + 1, vector(n));
st[0] = a;
for (int k = 1; k <= K; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
int query(int l, int r) {
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
};이 구현의 핵심은 query 함수 한 줄입니다. 질의 길이 이하의 가장 큰 power-of-two 길이를 찾고, 양 끝에서 길이 2k 구간 두 개를 가져와 최소를 비교합니다.
직접 손으로 따라가는 예시
예를 들어 query(1, 6) 을 한다고 해보겠습니다. 길이는 6이므로 가장 큰 power-of-two 는 4입니다. 그러면 [1,4] 와 [3,6] 두 구간을 봅니다.
두 구간이 겹치지만 괜찮습니다. 우리는 합이 아니라 최소를 구하기 때문입니다. 바로 이 중복 허용 성질이 희소 테이블을 빠르게 만드는 핵심입니다.
실전에서 자주 하는 실수
- 희소 테이블을 업데이트가 있는 문제에 억지로 적용한다
- 구간 합도 O(1) 이라고 착각한다
i + (1 << k) <= n범위를 잘못 잡아 인덱스 오류가 난다- log 배열이나
floor(log2(len))계산을 틀린다
특히 마지막 두 개는 구현 실수입니다. 개념은 맞는데 인덱스 범위를 틀려 오답이 나는 경우가 많으니, 작은 배열로 직접 표를 그려보는 습관이 도움이 됩니다.
RMQ에서 왜 특히 강할까
희소 테이블이 특히 RMQ에서 강한 이유는 중복을 허용해도 답이 깨지지 않기 때문입니다. 같은 원소를 두 번 포함해도 최소값은 달라지지 않으므로, 겹치는 두 구간을 바로 비교해도 안전합니다.
이 점이 바로 희소 테이블을 합 문제와 구분해야 하는 핵심입니다. 합은 중복되면 커지지만, 최소값은 중복돼도 그대로입니다.
정리
희소 테이블은 세그먼트 트리보다 더 어려운 구조가 아니라, 업데이트가 없는 구간 질의를 위해 문제를 더 정적으로 보는 방식입니다.
배열이 고정되어 있고 질의가 많으며, 최소값·최댓값처럼 중복 허용 연산을 반복해서 묻는다면 희소 테이블을 먼저 떠올릴 만합니다. 반대로 값이 바뀌면 세그먼트 트리로 돌아가야 합니다.
즉 이 글의 핵심은 하나입니다. 정적 RMQ라면 희소 테이블은 매우 강력하고, 그 강점은 O(1) 질의보다도 문제 전제가 명확하다는 데 있다고 기억하면 됩니다.
