Range Minimum Query

1정의#

길이 n인 배열 A₀, A₁, ⋯, A_n-1에서 구간 [l, r]의 최솟값 인덱스를 반환하는 쿼리를 구간 최솟값 쿼리(Range Minimum Query, RMQ)라 한다.

RMQ(l, r) = argmin { A_i : l ≤ i ≤ r }

2Cartesian 트리#

배열의 Cartesian 트리는 인덱스 순서 기준 이진 탐색 트리이면서 값 기준 최솟값 힙인 이진 트리다. 루트는 최솟값 인덱스이고, 왼쪽·오른쪽 서브트리는 각각 루트 기준 왼쪽·오른쪽 구간의 Cartesian 트리다.

블록 내 RMQ는 그 블록의 Cartesian 트리 형태만으로 결정된다. 크기 b인 배열에서 가능한 Cartesian 트리 형태의 수는 Catalan 수 C_b이다.

선형 시간에 구성할 수 있다.

3블록 분할#

블록 크기 b = ⌊log₂ n / 4⌋로 A를 블록 단위로 나눈다. 쿼리 [l, r]는 세 부분으로 분해된다.

• l이 속한 블록의 꼬리 → 블록 내부 룩업 테이블로 O(1)
• 중간 완전 블록들 → Sparse Table로 O(1)
• r이 속한 블록의 머리 → 블록 내부 룩업 테이블로 O(1)

4블록 최솟값 Sparse Table#

블록 수 B = ⌈n / b⌉에 대해, 각 블록의 최솟값 인덱스 M₀, ⋯, M_B-1을 O(n)에 계산한다. 이 배열에 Sparse Table을 적용하면 O(B log B) = O(n) 전처리, O(1) 쿼리가 가능하다.

5블록 내부 룩업 테이블#

크기 b인 블록의 Cartesian 트리 형태는 스택 구성 과정에서의 push·pop 순서를 비트 시퀀스로 인코딩하면 2b-1비트 이하로 표현된다(push b번, pop 최대 b-1번). 따라서 블록 유형은 최대 2^2b = 4^b가지다. b = ⌊log₂ n / 4⌋이면 4^b = O(√n)이다.

유형 t와 블록 내 구간 (l, r)에 대해 상대 최솟값 위치를 저장하는 테이블 in_block[t][l][r]을 미리 계산한다. 테이블 크기는 4^b · b² = O(√n · log² n) = O(n)이다.

각 블록의 유형 번호는 스택 구성 과정을 비트마스크로 인코딩하여 O(b)에 계산한다.

6시간 복잡도#

단계	시간 복잡도
전처리	O(n)
쿼리	O(1)

q개의 쿼리를 처리하는 총 시간은 O(n + q)이다.

7참고 문헌#

• Bender, M. A., & Farach-Colton, M. (2000). The LCA problem revisited. Latin American Symposium on Theoretical Informatics, 88–94.