Range Minimum Query

You are given an array $A[1..N]$. You have to answer incoming queries of the form $(L, R)$, which ask to find the minimum element in array $A$ between positions $L$ and $R$ inclusive.

RMQ can appear in problems directly or can be applied in some other tasks, e.g. the Lowest Common Ancestor problem.

Solution

There are lots of possible approaches and data structures that you can use to solve the RMQ task.

The ones that are explained on this site are listed below.

First the approaches that allow modifications to the array between answering queries.

And here are the approaches that only work on static arrays, i.e. it is not possible to change a value in the array without recomputing the complete data structure.

Note: Preprocessing is the preliminary processing of the given array by building the corresponding data structure for it.

Practice Problems