Sparse Table

Sparse Table이란 전체 N개의 원소들 중 임의의 원소 A에 대해, A를 바로 앞서서 있는 원소가 1개 이하 존재하는 상황에서, 원소 A의 K번째 앞에 있는 원소를 찾는 경우 사용하는 방법이다. (단, 임의의 원소 A를 바로 앞서서 있는 원소는 여럿일 수 있다. 즉, 원소 A의 바로 뒤에 있는 원소의 제한은 없다.)

'임의의 원소 A의 K번째 앞에 있는 원소를 찾아라' 라는 질문이 Q번 들어올 경우, 이를 해결하기 위해 Sparse Table이란 방법을 이용하여 빠르게 구할 수 있다.

Sparse Table을 이용하지 않고 가장 단순한 방법으로는 O(QN)의 시간복잡도를 가지는 방법이 있다.

Naive - O(QN)

A의 바로 앞 원소를 알고 있으므로, 쿼리마다 주어진 A에서 바로 앞으로 K번 이동하여 답을 구하는 방식으로 해결할 수 있다.

최악의 경우 이동 과정에서 N번 수행될 수 있으므로 시간복잡도 O(QN)을 갖는다.

위와 같은 Naive한 방법을 사용하는 대신, 전처리를 통해 Table을 만들어 쿼리의 처리 속도를 향상시킬 수 있다.

Sparse Table - O((N + Q)lgN)

임의의 원소 A에 대해, A의 2^i ( 0 <= i <= <lgN>) 번째 앞에 있는 원소를 기억하는 Table을 전처리로 구해놓는다.

이러한 Table을 작성하면, 쿼리마다 K번째 앞에 있는 원소를 최대 lgN의 수행을 거쳐서 구할 수 있고, 방법은 다음과 같다.

K를 이진수로 표현한 후, 이진수의 (자리가 1인 자릿수 - 1)을 각각 ai라고 하면, 모든 ai에 대해현재 원소 A에서 2^ai 번째에 해당하는 Table을 참조하여 현재 가리키는 원소를 A에서 A의 2^ai번째 앞에 있는 원소로 옮기는 작업을 수행해주면 첫 원소 A에서 K번째 앞에 있는 원소를 찾을 수 있다.

ex) K = 7 = 111(2) , 처음 가리키는 원소 A를 A의 2^2번째 앞, 이후 그 원소에서 2^1번째 앞, 이후 또 2^0번째 앞에 해당하는 원소를 참조하면 2^2 + 2^1 + 2^0 = 7번째 앞에 있는 원소를 찾을 수 있다.

전처리에 NlgN, 쿼리 처리에 QlgN의 시간이 들어가므로 전체 시간복잡도는 O((N + Q)lgN).

(공간복잡도는 Table을 저장하는 공간 NlgN)

이러한 전처리를 하는 Table을 바로 Sparse Table이라고 한다.

Sparse Table은 다음과 같은 점화식을 이용하여 계산할 수 있다.

Table[i][j] = (원소 j의 2^i번째 앞에 있는 원소)

i = 0 ) Table[0][j] = 원소 j의 바로 앞에 있는 원소

i > 0 ) Table[i][j] = Table[i - 1][Table[i - 1][j]]

원소 j의 2^i번째 앞에 있는 원소는, 원소 j의 2^(i - 1)번째 원소의 2^(i - 1)번째 원소임을 이용하여 Table을 채울 수 있다.