165. Sparse Table

희소 테이블(Sparse Table)은 정점마다 나가는 간선이 하나씩 존재하는 유향 그래프에서 사용할 수 있는 자료 구조로 어떤 정점에서 간선을 따라 여러 번 이동했을 때 어떤 정점에 도착하는지를 빠르게 구할 수 있다. 가끔씩 희소 배열(Sparse Array)이라고 표현하기도 하지만 이 단어는 다른 뜻이 많아 혼동하기 쉬워서 잘 쓰이지 않는다.

 

다음과 같은 그래프가 있을 때 정점 $\text{D}$에서 간선을 따라 $4$번 이동하면 정점 $\text{C}$에 도착한다.

각 정점에서 간선을 따라 이동했을 때 도착하는 정점을 이동 횟수에 따라 표로 나타내면 다음과 같다.

$0$	$\text{A}$	$\text{B}$	$\text{C}$	$\text{D}$	$\text{E}$	$\text{F}$	$\text{G}$
$1$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{A}$	$\text{C}$	$\text{C}$	$\text{F}$
$2$	$\text{F}$	$\text{C}$	$\text{F}$	$\text{B}$	$\text{B}$	$\text{B}$	$\text{C}$
$3$	$\text{C}$	$\text{B}$	$\text{C}$	$\text{F}$	$\text{F}$	$\text{F}$	$\text{B}$
$4$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{F}$
$5$	$\text{F}$	$\text{C}$	$\text{F}$	$\text{B}$	$\text{B}$	$\text{B}$	$\text{C}$
$6$	$\text{C}$	$\text{B}$	$\text{C}$	$\text{F}$	$\text{F}$	$\text{F}$	$\text{B}$
$7$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{F}$

정점의 수가 많지 않으면 이런 식으로 모든 정보를 다 저장해도 되지만, 정점이 $10$만 개쯤 되고 이동 횟수는 $100$만 번 정도까지 체크해야 하는 등 표가 너무 커지는 상황에는 이런 방식을 사용할 수 없다. 그런데 이 표를 자세히 보면 비슷한 부분들이 많이 보인다.

 

이전에 분할 정복을 이용한 거듭제곱을 소개할 때 $x^y$를 구하려면 $y$를 $2$의 거듭제곱의 합으로 나타내는 방식으로 분리해서 곱을 구할 수 있다고 했다. 비슷한 아이디어를 이 테이블에 적용해 보자. 다시 말해 정점 $v$에서 간선을 따라 $k$번 이동했을 때 도착하는 정점을 $f^k(v)$라고 하면 $f^x(f^y(v)) = f^{x+y}(v)$이므로 $k$가 $2$의 거듭제곱인 경우의 함숫값들만 알고 있으면 된다. 이 아이디어를 이용해서 아까와 같은 크기의 테이블을 다시 채우면 이렇게 된다.

$0$	$\text{A}$	$\text{B}$	$\text{C}$	$\text{D}$	$\text{E}$	$\text{F}$	$\text{G}$
$1$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{A}$	$\text{C}$	$\text{C}$	$\text{F}$
$2$	$\text{F}$	$\text{C}$	$\text{F}$	$\text{B}$	$\text{B}$	$\text{B}$	$\text{C}$
$4$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{F}$
$8$	$\text{F}$	$\text{C}$	$\text{F}$	$\text{B}$	$\text{B}$	$\text{B}$	$\text{C}$
$16$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{F}$
$32$	$\text{F}$	$\text{C}$	$\text{F}$	$\text{B}$	$\text{B}$	$\text{B}$	$\text{C}$
$64$	$\text{B}$	$\text{F}$	$\text{B}$	$\text{C}$	$\text{C}$	$\text{C}$	$\text{F}$

 

이 데이터를 조합하면 이동 횟수가 많아져도 함숫값을 빠르게 구할 수 있게 된다. 예를 들어 $f^{25}(\text{A})$를 구하려면 $f^1(f^8(f^{16}(\text{A})))$와 같이 세 번의 계산만 하면 된다. 물론 $f^{16}(f^8(f^1(\text{A})))$처럼 순서를 다르게 바꿔도 결과는 같다. 간선을 따라 이동한 횟수가 최대 $k$일 때 함수 계산은 최대 $\lceil \lg k \rceil$번 하게 되며 정점의 수가 $n$이면 대략 $n \lg k$만큼의 메모리를 사용하게 된다.

 

구현은 다음과 같이 할 수 있다.

#import<bits/stdc++.h>
using namespace std;
int st[20][100005]; // st는 sparse table의 약자로 사용됨
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> st[0][i]; // 초기 간선 정보 저장
    for(int p = 1; p < 20; p++)
    {
        for(int i = 1; i <= n; i++)st[p][i] = st[p - 1][st[p - 1][i]];
    }
}

$\text{st}[i][j]$는 $j$번 정점에서 간선을 따라 $2^i$번 이동했을 때 도착하는 정점의 번호와 같다. 이렇게 희소 테이블을 구성하면 함숫값은 다음과 같이 구할 수 있다.

int f(int v, int k)
{
    for(int i = 0; i < 20; i++)
    {
        if(k & 1 << i)v = st[i][v];
    }
    return v;
}

이제 정점 $v$에서 간선을 따라 $k$번 이동했을 때 도착하는 정점을 구하려면 $f(v, k)$를 호출하면 된다.

 

[연습문제]

 

BOJ 17435. 합성함수와 쿼리 (Gold I)

희소 테이블을 구성하여 합성함수의 값을 빠르게 구한다.

 

BOJ 10868. 최솟값 (Gold I)

세그먼트 트리를 사용하면 이런 문제를 풀 수 있다는 것이 알려져 있는데 값의 갱신이 없는 경우 희소 테이블을 사용해서 풀 수도 있다. $f(x, y)$를 $x$번째부터 $(x + 2^y - 1)$번째까지의 정수 중 최솟값으로 정의하고 구간의 길이보다 크지 않은 $2$의 거듭제곱 중에서 가장 큰 수가 $2^p$라고 하면 $\min(f(x, p), f(y - 2^p + 1, p))$를 구하면 된다.

 

BOJ 21214. Decoration (Platinum II)

$0$부터 $N - 1$까지의 약수의 개수를 에라토스테네스의 체를 이용해서 다 구한 다음 희소 테이블을 이용해서 수열의 합을 구한다. 이때 사이클이 있어서 초기 $K$항 중 같은 원소가 두 번 이상 등장하는 것들은 다 걸러내야 하기 때문에 추가적인 DFS가 필요하다.

 

→ solved.ac tag: sparse_table