RMQ

RMQ = Range Minimum Query

보통 범위가 작게 나올 경우, Bruteforce 방식으로 O(n^2) (n은 배열의 길이) 으로 가능하지만,

배열의 범위가 큰 경우에 시간초과가 날 수 있다.

이러한 경우, 

 1) (전처리 O(n)) O(루트n)시간안에 쿼리를 수행

    : 배열의 구간을 루트n으로 나누어 각각의 구간마다 최소값을 구한다.

 2) 전처리과정에서 O(nlogn), O(1) 쿼리 수행 가능

  :  이 경우 배열을 각 2의 승수 만큼의 인덱스 구간마다 정답을 모두 구해놓는 것으로 만일 RMQ(X,Y) (X~Y 인덱스 사이의 최소값) 를 구하기 위해서 RMQ(X,Z) 와 RMQ(P,Y) (P < Z 라는 조건) 를 구한 후 더 작은 최소값이 정답이 된다. 예를 하나 더 들자면 현재값에서 +1 , +2, +4 ... 인덱스 까지의 최소값을 구했다면 이 구간의 값을 이용하여 2^n 만큼의 구간나누기 DP가 가능하므로, nlogn 의 전처리과정이 가능한 것이다.

  !!! 이 경우는 제가 소스코드를 직접 짜보지 못해서, 검색을 통해 나온 블로그 첨부하겠습니다 :(  !!!

.            http://blog.sisobus.com/2013/11/range-minmaximum-query-rmq.html#.WoB5C6hl8dU

3) 전처리 과정에서 O(n), 쿼리 수행 O(nlogn) 가능

 : 펜윅트리 (Fenwick Tree) , Segment Tree 로 구현 가능. 구간별 최소값으로 트리를 구현하고, 따라서 트리의 탐색 시간복잡도인 nlogn 만큼의 시간복잡도가 수행된다.

펜윅트리와 세그먼트 트리는 비슷하지만 미묘하게 다른 쓰임이 있기 때문에 나누어서 설명하도록 하겠다.

 다음 챕터에서 펜윅트리를 그림을 통해 설명해보겠다.