Range minimum query

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 or the longest common prefix problem (LCP). 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 or the longest common prefix problem (LCP). Given an array A of n objects taken from a well-ordered set (such as numbers), the range minimum query RMQA(l,r) =arg min A (with 1 ≤ l ≤ k ≤ r ≤ n) returns the position of the minimal element in the specified sub-array A. For example, when A = , then the answer to the range minimum query for the sub-array A = is 7, as A = 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 of the array into a data structure 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 = min(A); 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. As in the solution above, answering queries in constant time will be achieved by pre-computing results. However, the array will store precomputed min queries for all elements and only the ranges whose size is a power of two. There are Θ(log n) such queries for each start position i, so the size of the dynamic programming table B is Θ(n log n). Each element B holds the index of the minimum of the range A. The table is filled with the indices of minima using the recurrence A query RMQA(l,r) can now be answered by splitting it into two separate queries: one is the pre-computed query with range from l to the highest boundary smaller than r. The other is the query of an interval of the same length that has r as its right boundary. These intervals may overlap, but as the minimum is computed rather than, say, the sum, this does not matter. The overall result can be obtained in constant time because these two queries can be answered in constant time and the only thing left to do is to choose the smaller of the two results. This solution answers RMQs in O(log n) time. Its data structures use O(n) space and its data structures can also be used to answer queries in constant time. The array is first conceptually divided into blocks of size s = log n/4. Then the minimum for each block can be computed in O(n) time overall and the minima are stored in a new array.