Range Minimum Query
Given an array of objects taken from a well-ordered set (such as numbers), a Range Minimum Query (or RMQ) from to asks for the position of a minimum element in the sub-array .
For example, when , then the answer to the range minimum query for the is , as .
In a typical setting, the array 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.
It is known that a -time preprocessing is sufficient to answer subsequent queries in time. The space of the resulting scheme is actually very small, namely bits (see Fischer & Heun (2007)).
- 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; Farach-Colton, Martin (2000), "The LCA Problem Revisited", Lecture Notes in Computer Science 1776, Springer-Verlag, pp. 88–94, doi:10.1007/10719839_9
- 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