희소 배열은 특정 구간에 대한 query를 빠르게 처리하기 위한 자료 구조이다. 주로 특정 구간의 최솟값, 최댓값, 합 등을 구할 때 모든 요소를 방문하지 않고 처리하기 위해 사용된다.
예시를 통해 확인해보자.
$f_{13}(x)$ 를 생각해보자. $f_{13}(x)$ 를 구하는 가장 쉬운 방법은 $f$ 를 13번 합성하는 것이다.
그러나 이는 쿼리 1개당 시간 복잡도가 $O(n)$ 이고, 전체 시간 복잡도는 $O(nQ)$ 인 비효율적인 방법이다.
$f$ 를 13번 합성하는 대신 $f_{13}(x)=f_{8}(f_{4}(f(x)))$ 로 표현할 수 있다.
$f_{2^{i}}(x)$ 를 매번 구하면 단순히 $f$ 를 13번 합성하는 것과 같은 시간 복잡도를 갖는다.
그러나 이 값들을 미리 저장을 한 뒤 매번 재사용할 수 있다. 이를 희소 배열이라고 한다.
위 문제에서 $f_{2^{i}}(x)=f_{2^{i-1}}(f_{2^{i-1}}(x))$ 의 점화식을 얻어낼 수 있으므로
희소 배열을 $arr[i][x]=f_{2^{i}}(x)$ 라고 정의하면 아래와 같은 방법으로 희소 배열의 값들을 구할 수 있다.
$for\;\;i\;=\;1\;\;to\;\;lg\;n$
$\;\;\;\;for\;\;j\;=1\;\;to\;\;m$
$\;\;\;\;\;\;\;\;arr[i][j]=arr[i-1][arr[i-1][j]]$
또한 $f_{k}(x)$ 를 구할 때 희소 배열을 이용해서 아래와 같이 해결할 수 있다.
$ans=x$
$for\;\;i\;=\;0\;\;to\;\;lg\;n$
$\;\;\;\;if(k\;\;\&\;\;(1<<i))$
$\;\;\;\;\;\;\;\;ans=arr[i][ans]$
$return\;\;ans$
시간 복잡도는 희소 배열을 구할 때 $O(m\;lg\;n)$ , 희소 배열을 이용해서 쿼리를 해결할 때 $O(Q\;lg\;n)$ 이므로 전체 알고리즘의 시간 복잡도는 $O((m+Q)\;lg\;n)$ 이다.
최소 공통 조상(LCA) 역시 희소 배열을 통해 해결할 수 있다. LCA에서 어떤 정점의 $n$ 번째 조상과 앞의 예제에 있던 $f_{n}(x)$ 과 같은 표현이다.
$u$ 와 $v$ 의 최소 공통 조상을 구하는 알고리즘은 2개의 부분으로 이루어져 있는데
1. $level[u]<level[v]$ 라고 가정할 때 $level[u]=level[v]$ 로 조정하는 작업
2. $u$ 와 $v$ 의 조상을 구해가며 $parent[u]==parent[v]$ 인지 확인하는 작업
으로 이루어져 있다.
첫번째 작업은 $k=level[v]-level[u]$ 라 했을 때 $f_{k}(u)$ 를 구하면 된다.
두번째 작업은 $i=lg\;N\;\;to\;\;1$ 에 대하여 $parent[u]\neq parent[v]$ 이면 $u=f_{i}(u)$ 를 실행하면 된다.
시간 복잡도는 $O((N+M)\;lg\;N)$ 이다.
마지막으로 특정 정점들 사이의 최솟값과 최댓값을 구하는데 활용할 수 있다. 먼저 그래프를 트리 형태로 재구성하여 LCA를 이용한다. 다음으로 희소 배열을 이용하는데, 구간에 대해서 $(1,\;2^{i})=(1,\;2^{i-1})+(2^{i-1}+1,\;2^{i})$ 를 이용하면
$(1,\;2^{i})$ 에서의 최솟값 = $(1,\;2^{i-1})$ 에서의 최솟값과 $(2^{i-1}+1,\;2^{i})$ 에서의 최솟값 중 더 작은 값
이라는 관계식을 도출해낼 수 있다. 이를 이용해서 희소 배열을 구할 때 구간의 최솟값, 최댓값도 미리 구할 수 있다.