Range Minimum Query

From Wikipedia, the free encyclopedia

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

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

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.