What is a Range Minimum Query (RMQ)?
An RMQ is a data structure used to perform operations such as min, max, gcd, lcm, and lca in constant time. An RMQ is similar to a segment tree, and it uses small intervals to maintain information about the array.
Range Minimum Query:
Building the RMQ:
A range-minimum query exists as a two-dimensional array. The length of the table is the same as the length of the array. The height of the table is (log2(length of array) rounded down + 1). Unlike a segment tree where each interval is completely disjoint from every other one, in RMQ there are overlaps. Here is a visualization of an RMQ table.
On the first row, each value just represents itself. On the second row, each index represents the value of the interval of length 2^1, starting from that index. On the third row, each index represents the value of the interval of length 2^2, starting from that index. Some boxes are crossed off because later indexes simply aren’t enough to have a length of 2^n.
Building the table only follows a couple of rules. RMQ tables will use values from the previous row to calculate the next row. First, fill the first row with the value that appears in the array since it represents intervals of 2^0. Then, simply follow the following line:
table[i] [j] = min(table[i-1][j], table[i-1][j + 2^(i-1)])
Querying the table:
RMQ’s are overlap-friendly. Which means the min(min([1,10]), min([3,15])) is the exact same as min([1,15]). Whenever there is a minimum, the value k must be found. K is the smallest n such that 2^n is less than the length of the requested interval. Once the k value is located, the two intervals that will be searched will be the following (L, R are the boundries): [L, L+k] and [R-1+k, R]. Go down to the 2^k row of the table and get the minimum (L, R-1+k). The number returned will be the answer to the query.
Querying the table:
RMQ’s are overlap friendly. Which means the the min(min([1,10]), min([3,15])) is the exact same as min([1,15]). Whenever an there is a minimum the value k must be found. K is the smallest n that 2^n is less than the length of the requested interval. Once the k value is located the two intervals that will be seachered will be the following (L, R are the boundries): [L, L+k] and [R-1+k, R]. Go down to the 2^k row of the table and get the min(L, R-1+k) the number returned will be the answer to the Query.
Other Applications of RMQ
One advantage of an RMQ is it’s ability to to get LCA in constant time. First, the an euler tour of the tree is done and the depth of each node is also recorded. Once the array of depths is made a minimum RMQ is formed from it. When the LCA is requested between two nodes a and b the LCA is lowest depth node between them.
Drawbacks of RMQ:
RMQ does provide an O(1) query but, there are issues with the other parts of the data s