선형 시간의 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}$ 가지 경우가 나온다.