콘텐츠로 이동

희소 테이블

희소 테이블은 구간 쿼리에 답할 수 있게 해 주는 자료 구조입니다. 대부분의 구간 쿼리에 $O(\log n)$에 답할 수 있지만, 진정한 강점은 구간 최솟값 쿼리(또는 이와 동등한 구간 최댓값 쿼리)에 답하는 데 있습니다. 이러한 쿼리에 대해서는 $O(1)$ 시간에 답을 계산할 수 있습니다.

이 자료 구조의 유일한 단점은 불변 배열에만 사용할 수 있다는 것입니다. 즉, 두 쿼리 사이에 배열을 변경할 수 없습니다. 배열의 원소가 하나라도 바뀌면 자료 구조 전체를 다시 계산해야 합니다.

직관

음이 아닌 모든 수는 감소하는 2의 거듭제곱들의 합으로 유일하게 나타낼 수 있습니다. 이는 수의 이진 표현을 변형한 것에 불과합니다. 예를 들어 $13 = (1101)_2 = 8 + 4 + 1$입니다. 수 $x$에 대해 항은 최대 $\lceil \log_2 x \rceil$개까지 있을 수 있습니다.

같은 논리로 모든 구간은 길이가 감소하는 2의 거듭제곱인 구간들의 합집합으로 유일하게 나타낼 수 있습니다. 예를 들어 $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$이며, 여기서 전체 구간의 길이는 13이고 개별 구간의 길이는 각각 8, 4, 1입니다. 그리고 여기서도 합집합은 최대 $\lceil \log_2(\text{length of interval}) \rceil$개의 구간으로 이루어집니다.

희소 테이블의 핵심 아이디어는 길이가 2의 거듭제곱인 구간 쿼리에 대한 모든 답을 미리 계산해 두는 것입니다. 그 후 다른 구간 쿼리는 구간을 길이가 2의 거듭제곱인 구간들로 나누고, 미리 계산된 답을 찾아본 뒤, 이를 결합하여 전체 답을 얻는 방식으로 답할 수 있습니다.

전처리

미리 계산된 쿼리의 답을 저장하기 위해 2차원 배열을 사용하겠습니다. $\text{st}[i][j]$에는 길이가 $2^i$인 구간 $[j, j + 2^i - 1]$에 대한 답이 저장됩니다. 2차원 배열의 크기는 $(K + 1) \times \text{MAXN}$이며, 여기서 $\text{MAXN}$은 가능한 가장 큰 배열 길이입니다. $2^{\lfloor \log_2 \text{MAXN} \rfloor}$이 지원해야 하는 가장 큰 2의 거듭제곱 길이의 구간이므로, $\text{K}$는 $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor$을 만족해야 합니다. 적당한 길이($\le 10^7$개의 원소)의 배열이라면 $K = 25$가 좋은 값입니다.

$\text{MAXN}$ 차원을 두 번째로 두는 것은 (캐시 친화적인) 연속적 메모리 접근을 가능하게 하기 위함입니다.

int st[K + 1][MAXN];

길이가 $2^i$인 구간 $[j, j + 2^i - 1]$은 둘 다 길이가 $2^{i - 1}$인 구간 $[j, j + 2^{i - 1} - 1]$과 $[j + 2^{i - 1}, j + 2^i - 1]$로 깔끔하게 나뉘므로, 동적 계획법을 사용하여 테이블을 효율적으로 생성할 수 있습니다:

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

함수 $f$는 쿼리의 종류에 따라 달라집니다. 구간 합 쿼리의 경우 합을 계산하고, 구간 최솟값 쿼리의 경우 최솟값을 계산합니다.

전처리의 시간 복잡도는 $O(\text{N} \log \text{N})$입니다.

구간 합 쿼리

이 종류의 쿼리에서는 구간 내 모든 값의 합을 구하고자 합니다. 따라서 함수 $f$의 자연스러운 정의는 $f(x, y) = x + y$입니다. 다음과 같이 자료 구조를 구성할 수 있습니다:

long long st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

구간 $[L, R]$에 대한 합 쿼리에 답하기 위해, 가장 큰 것부터 시작하여 모든 2의 거듭제곱을 순회합니다. 2의 거듭제곱 $2^i$가 구간의 길이($= R - L + 1$)보다 작거나 같아지는 즉시, 구간의 첫 부분 $[L, L + 2^i - 1]$을 처리하고 나머지 구간 $[L + 2^i, R]$로 계속 진행합니다.

long long sum = 0;
for (int i = K; i >= 0; i--) {
    if ((1 << i) <= R - L + 1) {
        sum += st[i][L];
        L += 1 << i;
    }
}

구간 합 쿼리의 시간 복잡도는 $O(K) = O(\log \text{MAXN})$입니다.

구간 최솟값 쿼리 (RMQ)

이러한 쿼리야말로 희소 테이블이 빛을 발하는 쿼리입니다. 구간의 최솟값을 계산할 때는 구간 안의 값을 한 번 처리하든 두 번 처리하든 상관이 없습니다. 따라서 구간을 여러 구간으로 나누는 대신, 길이가 2의 거듭제곱이면서 서로 겹치는 두 구간으로만 나눌 수도 있습니다. 예를 들어 구간 $[1, 6]$을 구간 $[1, 4]$와 $[3, 6]$으로 나눌 수 있습니다. $[1, 6]$의 구간 최솟값은 $[1, 4]$의 구간 최솟값과 $[3, 6]$의 구간 최솟값 중 더 작은 값과 분명히 같습니다. 따라서 구간 $[L, R]$의 최솟값은 다음과 같이 계산할 수 있습니다:

$$\min(\text{st}[i][L], \text{st}[i][R - 2^i + 1]) \quad \text{ where } i = \log_2(R - L + 1)$$

이를 위해서는 $\log_2(R - L + 1)$을 빠르게 계산할 수 있어야 합니다. 모든 로그값을 미리 계산해 두면 이를 해결할 수 있습니다:

int lg[MAXN+1];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i/2] + 1;
또는 로그를 상수 공간과 상수 시간에 즉석에서 계산할 수도 있습니다: 
// C++20
#include <bit>
int log2_floor(unsigned long i) {
    return std::bit_width(i) - 1;
}

// pre C++20
int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}
이 벤치마크는 lg 배열을 사용하는 방법이 캐시 미스 때문에 더 느리다는 것을 보여 줍니다.

그다음에는 희소 테이블 구조를 미리 계산해야 합니다. 이번에는 $f$를 $f(x, y) = \min(x, y)$로 정의합니다.

int st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

그리고 구간 $[L, R]$의 최솟값은 다음과 같이 계산할 수 있습니다:

int i = lg[R - L + 1];
int minimum = min(st[i][L], st[i][R - (1 << i) + 1]);

구간 최솟값 쿼리의 시간 복잡도는 $O(1)$입니다.

더 많은 종류의 쿼리를 지원하는 유사한 자료 구조

앞 절에서 다룬 $O(1)$ 방식의 주요 약점 중 하나는 이 방식이 멱등 함수에 대한 쿼리만 지원한다는 점입니다. 즉, 구간 최솟값 쿼리에는 매우 잘 작동하지만, 이 방식으로 구간 합 쿼리에 답하는 것은 불가능합니다.

결합 법칙을 만족하는 임의의 함수를 처리하면서 구간 쿼리에 $O(1)$에 답할 수 있는 유사한 자료 구조들이 있습니다. 그중 하나는 Disjoint 희소 테이블입니다. 또 다른 하나는 Sqrt 트리입니다.

연습 문제