알고리즘: RMQ

RMQ(Range Minimum Query):

(query란 단어의 뜻은 문의하다, 질문하다) 참고자료

숫자가 n개 있는 배열이 하나 있고, 해결해야 하는 (l,r)의 쿼리가 q개 들어오는 상황 기준

1. Brute Force

q(l,r)일 때 l부터 r까지 전부 훑어서 RMQ를 찾음.

전처리: x

시간 복잡도: O(n)

업데이트: O(n) 

직관적이고 쉬움, 배열의 값을 업데이트하는 것이 자유로움.

2. 미리 전부 전처리

전처리로 테이블을 미리 만들어 놓고 테이블에서 가져옴

전처리: O(n^2)

시간복잡도: O(1)

업데이트: O(n^2) 

시간복잡도가 낮으나 전처리가 길고, 배열의 값을 하나만 바꿔도 테이블을 O(n^2)을 들여 만들어야 함

3. Sqrt Decomposition

root(n)개로 n을 조각낸 뒤 각각의 테이블을 만들어 접근.

전처리: O(n)

업데이트: O(root(n))

시간복잡도: O(root(n))

쿼리 당 걸리는 시간이 꽤 적고, 업데이트가 빠른 시간 내에 가능.

4. Sparse Table

모든 k에 대해 연속적인 길이 2^k의 최솟값을 미리 구함.

전처리: O(n log n)

시간복잡도: O(1)