RMQ (Range Minimum Query)
RMQ, Range Minimum Query, 구간 최솟값
정의
Range Minimum Query 는 배열 A 에 대해 구간 [l, r] 의 최솟값을 답하는 문제입니다. 최댓값, gcd, XOR 등으로 자연스럽게 일반화됩니다.
방법 비교
| 방법 | 전처리 | 쿼리 | 갱신 |
|---|---|---|---|
| 순회 | O(1) | O(N) | O(1) |
| [[sparse-table | Sparse Table]] | O(N log N) | O(1) |
| [[segtree | Segment Tree]] | O(N) | O(log N) |
| Sqrt Decomposition | O(N) | O(√N) | O(1) |
| ±1 RMQ (LCA용) | O(N) | O(1) | 지원 안 함 |
LCA -> RMQ
트리의 Euler tour 상 두 정점 등장 사이에서 depth 최솟값 이 LCA. RMQ 를 O(1) (sparse table) 로 답하면 LCA 도 O(1) 쿼리 가능.
참고
이 글의 용어 (4개)
- 세그먼트 트리 (Segment Tree)algorithm
- 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
- 오일러 투어 테크닉 (Euler Tour Technique)algorithm
- 정의 오일러 투어 테크닉 (ETT, Euler Tour Technique) 은 트리를 DFS 방문 순서로 펼쳐 서브트리 쿼리를 구간 쿼리로 변환하는 정형. 각 노드 u 의 in-…
- 최소 공통 조상 (Lowest Common Ancestor)algorithm
- 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…
- 희소 배열 (Sparse Table)algorithm
- 정의 희소 배열 (Sparse Table) 은 정적 배열에서 결합 법칙을 만족하는 idempotent 연산 (min, max, gcd, lcm 등) 의 구간 쿼리를 O(1) 시간…
💬 댓글