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.

Given an array A[1 … n] of n objects taken from a totally ordered set, such as integers, the range minimum query RMQA(l,r) =arg min A[k] (with 1 ≤ l ≤ k ≤ r ≤ n) returns the position of the minimal element in the specified sub-array A[l … r].

In this case a suitable preprocessing of the array into a data structure ensures faster query answering.

Using the solution above, the sub-queries inside the blocks that are not fully contained in the query still need to be answered in constant time.

To look up results efficiently, the Cartesian tree (row) corresponding to a specific block must be addressable in constant time.

The integer is then generated by representing every inner node as a 0-bit and every leaf as a 1-bit in a bit-word (by traversing the tree in level-order again).

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

The LCA query LCAS(v, w) of a rooted tree S = (V, E) and two nodes v, w ∈ V returns the deepest node u (which may be v or w) on paths from the root to both w and v. Gabow, Bentley, and Tarjan (1984) showed that the LCA Problem can be reduced in linear time to the RMQ problem.

Constructing the corresponding Cartesian tree to solve a range minimum query.
Range minimum query reduced to the lowest common ancestor problem.
Example of Cartesian trees for A = [0,5,2,5,4,3,1,6,3] . Notice that the first and third tree have the same layout, so there are exactly two pre-computed sets of queries in the table on the left.