Range minimum query
Given an array A[1…n] of n objects taken from a well-ordered set (such as numbers), a range minimum query (or range min query, RMQ) asks for the position of a minimum element in some sub-array A[i…j]. While this problem can be trivially solved in linear time, it can be solved faster if the array A is preprocessed into a custom data structure.
For example, when A = [0,5,2,5,4,3,1,6,3], then the answer to the range minimum query for the A[3…8] = [2,5,4,3,1,6] is 7, as A = 1.
In a typical setting, the array A is static, i.e., elements are not inserted or deleted during a series of queries, and the queries to be answered on-line (i.e., the whole set of queries are not known in advance to the algorithm). In this case a suitable preprocessing the array into a data structure (often called a preprocessing scheme) ensures faster query answering. A naïve solution is to precompute all possible queries, i.e. the minimum of all sub-arrays of A, and store these in an array B such that B[i, j] = min(A[i…j]); then a range min query can be solved in constant time by array lookup in B. There are Θ(n²) possible queries for a length-n array, and the answers to these can be computed in Θ(n²) time by dynamic programming.
It is known that a O(n)-time preprocessing is sufficient to answer subsequent queries in O(1) time. The space of the resulting scheme is actually very small, namely O(n) bits.
- Berkman, Omer; Vishkin, Uzi (1993). "Recursive Star-Tree Parallel Data Structure". SIAM Journal on Computing 22 (2): 221–242. doi:10.1137/0222017.
- Bender, Michael A.; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2005). "Lowest common ancestors in trees and directed acyclic graphs". Journal of Algorithms 57 (2): 75–94.
- Fischer, Johannes; Heun, Volker (2007), "A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array", Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science 4614, Springer-Verlag, pp. 459–470, doi:10.1007/978-3-540-74450-4_41
- Bender, Michael; Farach-Colton, Martín (2000), "The LCA Problem Revisited", Lecture Notes in Computer Science 1776, Springer-Verlag, pp. 88–94, doi:10.1007/10719839_9