희소 테이블(Sparse Table)은 범위 쿼리(range query)의 결과를 빠르게 구하기 위해 사용되는 자료구조입니다. 대부분의 범위 쿼리를 O(logN) 시간 복잡도로 처리할 수 있으며, 특히 구간 최댓값(maximum) 쿼리는 O(1)만에 답을 계산할 수 있습니다.
이 글에서는 주어진 배열에서 인덱스 L부터 R까지 구간에 포함된 모든 원소의 합을 구하는 범위 합(Range Sum) 쿼리 문제를 희소 테이블을 이용해 해결하는 방법을 살펴보겠습니다.
입력: arr[] = { 2, 4, 1, 5, 6, 3 }
query(1, 3)
query(0, 2)
query(1, 5)
출력:
10
7
19
입력: arr[] = { 1, 2, 3, 4, 1, 4 }
query(0, 2)
query(2, 4)
query(3, 5)
출력:
6
8
9문제 해결 접근 방식
쿼리의 답을 빠르게 조회하려면 먼저 희소 테이블을 구축해야 합니다. 희소 테이블은 2차원 배열 형태로 답을 미리 저장하며, 각 구간을 2의 거듭제곱 크기로 나누어 관리한다는 것이 핵심 아이디어입니다.
희소 테이블의 구조
- SPARSE[i][0] = arr[i] : 인덱스 i에서 시작하는 길이 1(2⁰) 구간의 합
- SPARSE[i][j] = SPARSE[i][j-1] + SPARSE[i + 2^(j-1)][j-1] : 인덱스 i에서 시작하는 길이 2^j 구간의 합을 두 개의 절반 구간 합으로 계산
쿼리 처리 과정
[L, R] 구간의 합을 구할 때는 왼쪽 끝(L)부터 시작해, Left_index + 2^n - 1 <= Right_index 조건을 만족하는 가장 큰 2^n 크기의 블록을 찾아 그 값을 누적하고, L을 해당 블록 크기만큼 앞으로 이동시키는 작업을 반복합니다. n은 2차원 배열의 열(column) 크기를 의미합니다.
C++ 구현 예제
다음은 위 접근 방식을 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
// 희소 테이블의 최대 행(row) 크기
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// 희소 테이블을 이용해 범위 합을 구하는 쿼리 함수
long long query(int l, int r){
long long sum = 0;
for (int i = n; i >= 0; i--) {
if (l + (1 << i) - 1 <= r) {
sum = sum + SPARSE[l][i];
l += 1 << i;
}
}
return sum;
}
int main(){
int arr[] = { 1, 2, 3, 4, 1, 4 };
int z = sizeof(arr) / sizeof(arr[0]);
// 희소 테이블 구축
for (int i = 0; i < z; i++)
SPARSE[i][0] = arr[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j + (1 << i) <= z; j++)
SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1];
cout << "Sum: " << query(0, 2) << endl;
cout << "Sum: " << query(2, 4) << endl;
cout << "Sum: " << query(3, 5) << endl;
return 0;
}실행 결과
Sum: 6 Sum: 8 Sum: 9
배열 {1, 2, 3, 4, 1, 4}에서 query(0, 2)는 1+2+3=6, query(2, 4)는 3+4+1=8, query(3, 5)는 4+1+4=9로 올바른 결과가 출력됩니다.
시간 복잡도
- 전처리(테이블 구축) : O(N logN)
- 쿼리당 처리 시간 : O(logN) — 구간을 2의 거듭제곱 블록으로 분해하며 합산
따라서 같은 배열에 대해 수많은 범위 합 쿼리를 반복해야 하는 상황이라면, 매번 O(N)으로 구간을 순회하는 단순 방식보다 희소 테이블이 훨씬 효율적입니다.
마무리
이 글에서는 범위 쿼리에 매우 유용한 자료구조인 희소 테이블을 만드는 방법을 다루었습니다. 희소 테이블을 구축한 뒤 해당 테이블에서 쿼리 결과를 조회하는 간단한 접근 방식을 살펴보았고, 이를 C++ 프로그램으로 구현했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮길 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되었기를 바랍니다.