In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP).
Given an array of objects taken from a totally ordered set, such as integers, the range minimum query (with) returns the position of the minimal element in the specified sub-array .
For example, when, then the answer to the range minimum query for the sub-array 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 of the array into a data structure ensures faster query answering. A naive solution is to precompute all possible queries, i.e. the minimum of all sub-arrays of, and store these in an array such that ; then a range min query can be solved in constant time by array lookup in . There are possible queries for a length- array, and the answers to these can be computed in time by dynamic programming.[1]
As in the solution above, answering queries in constant time will be achieved by pre-computing results. However, the array will store pre-computed range minimum queries not for every range, but only for ranges whose size is a power of two. There are such queries for each start position, so the size of the dynamic programming table is . The value of is the index of the minimum of the range . Filling the table takes time, with the indices of minima using the following recurrence
If
