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 be applied to other tasks, including Lowest Common Ancestor.


RMQ task is solved by using appropriate data structures.

From the list of data structures described on this site, you can choose:

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

If the array $A$ might change during the runtime (i.e. there will also be queries to change values in some interval), the problem can only be solved by Sqrt-decomposition or Segment tree.

Practice Problems