선형 시간의 Range Minimum Query Range Minimum Query(RMQ)는 세그먼트 트리를 이용하면 $O(N)$ 시간에 전처리, $O(logN)$ 시간에 쿼리를 구할 수 있고, Sparse Table을 이용하면 $O(NlogN)$ 시간에 전처리, $O(1)$에 쿼리를 할 수 있다.그런데 시간복잡도만 보면 위의 두 방법보다 빠른 $O(N)$ 전처리와 $O(1)$ 쿼리를 하는 것이 가능하다고 한다. 길이 $N$의 수열을 크기가 $K$인 구간들로 나누자. 구간의 개수는 $\frac{N}{K}$가 될 것이다. 이제 구간 쿼리는 min(쿼리에 포함되는 연속된 구간들의 RMQ, 왼쪽 끝점이 포함된 구간에서의 RMQ, 오른쪽 끝점이 포함된 구간에서의 RMQ)으로 쓸 수 있다. 이제 연속된 구간의 RMQ, 한 구간 내에서의 RMQ를 $O(1)$에.. 더보기 이전 1 ··· 5 6 7 8 9 10 11 ··· 24 다음