19. 희소 배열 (Sparse table, c++)

희소 배열 (Sparse table)?

앞서 구간에 대한 합계를 Prefix Sum을 이용해 계산을 했다면, 구간에 대해 최소값 또는 최대값을 계산하는 것은 조금 더 복잡한 문제입니다.

 

Sparse table 을 이용하면 O(nlogn)의 전처리 이후 구간에 대한 최소값과 최대값을 구하는 것을 O(1) 시간복잡도로 수행할 수 있습니다.

 

Sparse 라는 단어는 가능한 모든 구간을 저장하는 것이 아니라, 2의 거듭제곱 길이의 구간만 저장하기 때문에 붙여진 이름입니다.

 

모든 정수는 2의 거듭제곱을 한번씩 사용해서 표현할 수 있습니다.

 

당연하게도 모든 정수들은 이진수로 표현할 수 있고 7은 111, 9는 1001 이기 때문입니다.

 

예를 들면, 7은 4+2+1 이고 9는 8+1 과 같은 형태입니다.

 

이러한 원리를 이용하면 9개의 구간에 대해 검사를 할때, 8개+1개와 같이 2의 거듭제곱 길이의 구간들의 조합으로 효율적으로 계산할 수 있습니다.

---

Implementation

 

전처리 단계에서는 배열의 모든 2의 거듭제곱 길이 구간에 대한 대표값(최대값, 최소값 등)을 미리 계산하여 저장합니다.

 

이 과정은 O(NlogN)의 시간이 소요됩니다.

 

{ 1, 3, 4, 8, 6, 1, 4, 2 } 배열에 대해 구간의 최소값을 구하는 연산을 하려고 합니다.

 

d[k][n]에는 n에 대한 2의 k승 구간에 대한 최소값을 저장합니다.

 

예를 들어, k=0 이면 2^0인 1 즉 n부터 1개의 구간에 대한 최소값을 저장하고

 

k=2 이면 2^2인 4 즉 n부터 4개의 구간에 대한 최소값을 저장합니다. (n이 1이라면 1~4 구간에 대한 최소값)

 

우선 k는 2의 거듭제곱이 주어진 n을 초과하지 않는 최대 정수입니다.

 

N이 10 이라면 최대로 필요한 K는 2^3=8 이므로 K는 4가 됩니다.

    int K = 0;
    while ((1<<K) <= N) K++;

 

다음으로 d[0][n] 은 자기 자신입니다.

 

d[k][n] 은 다이나믹 프로그래밍을 적용해 이전 단계에 계산된 값을 이용해 구할 수 있습니다.

 

n이 1일때,

 

k=1 일때는 2개의 구간을 나타내므로 자신의 0번째 구간(1~1) 과 자신+(2^k-1)의 0번째 구간(2~2) 중 최소값을 구해 1~2 구간의 최소값을 구합니다.

 

k=2 일때는 4개의 구간을 나타내므로 자신의 1번째 구간(1~2)과 자신+(2^k-1)의 1번째 구간(3~4) 중 최소값을 구해 1~4 구간의 최소값을 구합니다.

 

모든 단계에서 2^K 길이 구간을 2^K-1 구간 두개로 나누어 최소값을 계산합니다.

    REP(k, 1, K) {
        REP(i, 1, N+1) {
            d[k][i] = min(d[k-1][i], d[k-1][i+(1<<(k-1))]);
        }
    }

 

구해진 값은 아래와 같게 됩니다. 0은 표현할 수 있는 구간이 없어서 무의미한 값 입니다.

K\N	1	3	4	8	6	1	4	2
0	1	3	4	8	6	1	4	2
1	1	3	4	6	1	1	2	0
2	1	3	1	1	1	0	0	0
3	1	0	0	0	0	0	0	0

 

전처리가 끝났다면 구간에 대한 쿼리는 O(1)에 수행할 수 있습니다.

 

A~B까지 구간에 대한 최소값을 구한다면 구간의 길이를 넘지않는 최대 2의 거듭제곱을 구합니다.

 

그리고 A에서부터 우측으로 2^K개와 B에서부터 좌측으로 2^K개의 구간을 검사하면 구해둔 값을 이용하여 값을 구할 수 있습니다.

 

예를 들어 1~8 구간에 대해 최소값을 구한다면, 총 구간의 길이는 8개이므로 k는 3입니다.

 

1에서부터 우측으로 2^3개는 d[3][1] 에 구해져 있습니다. (1~8)

8에서부터 좌측으로 2^3개는 8에서 2^3개 이전 구간부터 8까지와 동일하므로 d[3][1] 입니다. (1~8)

 

두개의 최소값을 구하면 1 입니다. 

 

이번에는  2~7 구간에 대해 최소값을 구한다면, 총 구간의 길이는 6 이므로 k는 2입니다.

 

2에서부터 우측으로 2^2개는 d[2][2]에 구해져 있습니다. (2~5)

 

7에서부터 좌측으로 2^2개는 7에서 2^2개 이전 구간부터 7까지 이므로 d[2][4] 입니다. (4~7)

 

두개의 최소값을 구하면 1 입니다.

 

좌측에서 대표하는 범위

O

O

O

O

 

우측에서 대표하는 범위

O

O

O

O

 

전체 범위

O

O

O

O

O

O

 

범위 내에서 구하고자하는 모든 구간의 최소값은 항상 두개의 구간으로 분리해 O(1)에 계산할 수 있습니다.

        int length = b-a+1;
        int k = log2(length);

        cout << min(d[k][a], d[k][b-(1<<k)+1]) << "\n";