선형 시간의 Range Minimum Query

Range Minimum Query(RMQ)는 세그먼트 트리를 이용하면 $O(N)$ 시간에 전처리, $O(\log N)$ 시간에 쿼리를 구할 수 있고, Sparse Table을 이용하면 $O(N \log N)$ 시간에 전처리, $O(1)$에 쿼리를 할 수 있다.

그런데 시간복잡도만 보면 위의 두 방법보다 빠른 $O(N)$ 전처리와 $O(1)$ 쿼리를 하는 것이 가능하다고 한다.

길이 $N$의 수열을 크기가 $K$인 구간들로 나누자. 구간의 개수는 $\frac{N}{K}$가 될 것이다. 이제 구간 쿼리는 min(쿼리에 포함되는 연속된 구간들의 RMQ, 왼쪽 끝점이 포함된 구간에서의 RMQ, 오른쪽 끝점이 포함된 구간에서의 RMQ)으로 쓸 수 있다. 이제 연속된 구간의 RMQ, 한 구간 내에서의 RMQ를 $O(1)$에 처리하면 된다.

1. 연속된 구간들의 RMQ

연속된 구간들의 RMQ는 Sparse table을 이용하면 $O(\frac{N}{K}\log\frac{N}{K})$ 전처리, $O(1)$ 쿼리가 가능하다.

2. 구간 내에서의 RMQ

$K$ 크기의 구간에서 RMQ는, Cartesian Tree에서의 LCA와 같은 의미이다. Cartesian Tree는 $O(K)$에 구할 수 있다.

Cartesian Tree에서 LCA를 구하기 위해서 Euler Tour 배열을 만든다. Euler Tour의 크기는 $2K-1$이 된다. Euler Tour 배열에서 각 노드들의 높이를 모두 안다면, 모든 쿼리에 대해서 LCA가 몇 번째 원소인지도 결정할 수 있다. 따라서 수열에서 등장하는 모든 구간들의 Cartesian Tree의 모양에 대해서 $O(K^2)$에 가능한 모든 쿼리들을 전처리해두면 $O(1)$에 쿼리를 처리할 수 있다.

$K$ 크기의 구간에서 Euler Tour 높이 배열은 몇 가지 종류나 있을까? Euler Tour의 인접한 원소는 높이 차이가 $1$이기 때문에, $2K-2$개의 $\pm 1$들로 Euler Tour 전체를 표현할 수 있다. 이것을 비트마스킹으로 표현할 수 있고, 따라서 총 $2^{2K-2}$가지 경우가 나온다.

Cartesian Tree와 Euler Tour를 만드는 것이 총 $O(N)$이고, $2^{2K-2}$개 종류의 Cartesian Tree에 대해 $O(K^2)$에 전처리하므로 $O(2^{2K}K^2)$이 된다.

1번과 2번 과정의 전처리 복잡도를 합하면 $O(N+\frac{N}{K}\log\frac{N}{K}+2^{2K}K^2)$이 된다.

$K=\frac{\log N}{4}$로 정하면 복잡도는

$$\begin{aligned}&\quad O(N+4N\times\frac{\log N-\log \log N+2}{\log N}+\sqrt{2}^{\log N}\log^2N)\\&=O(N+\sqrt{N}\log^2N)\\&=O(N)\end{aligned}$$

이 된다.

따라서 $O(N)$ 전처리, $O(1)$ 쿼리가 된다. 이 방법이 실제로 세그먼트 트리나 Sparse Table보다 빠른 상황은 많지 않을듯 하다.