Range minimum query

From Wikipedia, the free encyclopedia
  (Redirected from Range Minimum Query)
Jump to: navigation, search
A Constructing the corresponding cartesian tree to solve a range minimum query.
Range minimum query reduced to the lowest common ancestor problem.

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[ij]. 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[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. 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[ij]); 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.[1]

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

RMQs can be used to solve the lowest common ancestor problem[1][3] and are used as a tool for many tasks in exact and approximate string matching.

See also[edit]

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. 
  1. ^ a b 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. doi:10.1016/j.jalgor.2005.08.001. 
  2. ^ 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. LNCS 4614. Springer. pp. 459–470. doi:10.1007/978-3-540-74450-4_41. 
  3. ^ Bender, Michael; Farach-Colton, Martín (2000). "The LCA Problem Revisited". LATIN 2000: Theoretical Informatics. LNCS 1776. Springer. pp. 88–94. doi:10.1007/10719839_9. 

External links[edit]