RMQ

RMQ stands for Range Minimum Query. Given an array A of length n, RMQ(i, j) returns the minimum element in the subarray A[i..j], often by returning either the value or the index of the minimum element. Queries are typically assumed to use 0-based indices with i <= j.

Variants of RMQ differentiate whether the array is static or dynamic, whether the minimum value or its position is returned, and whether indices are 0-based or 1-based. In many treatments, the focus is on 0-based indices and on returning the value or the index of the minimum element for a given range.

Static RMQ data structures allow fast queries after a preprocessing phase that does not need to handle updates. The most common approach is the sparse table, which preprocesses in O(n log n) time and O(n log n) space and answers queries in O(1) time by combining the minima of two overlapping blocks. There are more advanced variants, such as the Fischer–Heun method, which achieves O(1) queries with linear space but is more complex to implement.

Dynamic RMQ supports updates to the array. The standard solution is a segment tree, which provides O(log n) time for both queries and updates. Other approaches include sqrt-decomposition and various balanced-tree based structures, chosen based on workload characteristics.

RMQ has notable applications, including its use in computing the lowest common ancestor (LCA) of nodes in a tree via an Euler tour representation. After suitable preprocessing, RMQ enables fast LCA queries, which in turn support various algorithms in graph theory and computational biology, among other fields.