구간 최솟값 쿼리¶
배열 $A[1..N]$이 주어집니다. $(L, R)$ 형태로 들어오는 쿼리에 답해야 하며, 각 쿼리는 배열 $A$에서 위치 $L$부터 $R$까지(양 끝 포함)의 최솟값 원소를 구하도록 요구합니다.
RMQ는 문제에 직접 등장할 수도 있고, 최소 공통 조상 문제처럼 다른 문제에 응용될 수도 있습니다.
풀이¶
RMQ 문제를 푸는 데 사용할 수 있는 접근법과 자료 구조는 매우 많습니다.
이 사이트에서 설명하는 것들은 아래와 같습니다.
먼저 쿼리에 답하는 사이사이에 배열을 수정할 수 있는 접근법입니다.
- 제곱근 분할법 - 각 쿼리에 $O(\sqrt{N})$에 답하며, 전처리는 $O(N)$에 수행합니다. 장점: 매우 간단한 자료 구조입니다. 단점: 복잡도가 더 나쁩니다.
- 세그먼트 트리 - 각 쿼리에 $O(\log N)$에 답하며, 전처리는 $O(N)$에 수행합니다. 장점: 시간 복잡도가 좋습니다. 단점: 다른 자료 구조에 비해 코드 양이 많습니다.
- 펜윅 트리 - 각 쿼리에 $O(\log N)$에 답하며, 전처리는 $O(N \log N)$에 수행합니다. 장점: 코드가 가장 짧고, 시간 복잡도가 좋습니다. 단점: RMQ용 표준 펜윅 트리는 접두사 쿼리($L = 1$)만 지원합니다.
다음은 정적 배열에서만 동작하는 접근법입니다. 즉, 자료 구조 전체를 다시 계산하지 않고서는 배열의 값을 변경할 수 없습니다.
- 희소 테이블 - 각 쿼리에 $O(1)$에 답하며, 전처리는 $O(N \log N)$에 수행합니다. 장점: 자료 구조가 간단하고, 시간 복잡도가 매우 뛰어납니다.
- Sqrt 트리 - 쿼리에 $O(1)$에 답하며, 전처리는 $O(N \log \log N)$에 수행됩니다. 장점: 빠릅니다. 단점: 구현이 복잡합니다.
- 서로소 집합 유니온 / Arpa의 트릭 - 쿼리에 $O(1)$에 답하며, 전처리는 $O(n)$에 수행합니다. 장점: 짧고 빠릅니다. 단점: 모든 쿼리를 미리 알고 있을 때만 동작합니다. 즉, 쿼리의 오프라인 처리만 지원합니다.
- 데카르트 트리와 Farach-Colton과 Bender 알고리즘 - 쿼리에 $O(1)$에 답하며, 전처리는 $O(n)$에 수행합니다. 장점: 복잡도가 최적입니다. 단점: 코드 양이 많습니다.
참고: 전처리란 주어진 배열에 대응하는 자료 구조를 구축하여 배열을 미리 처리하는 작업을 말합니다.