Range Minimum Query

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Given an array A[1,n] of n objects taken from a well-ordered set (such as numbers), a Range Minimum Query (or RMQ) from i to j asks for the position of a minimum element in the sub-array A[i,j].

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[7]=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.

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 (see Fischer & Heun (2007)).

RMQs can be used to solve the lowest common ancestor problem, and is used as a tool for many tasks in exact and approximate string matching.

References[edit]

  • 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 

External links[edit]