# 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.

## Solution

RMQ task is solved by using appropriate data structures.

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

- Sqrt-decomposition - answers each query in $O(\sqrt{N})$, preprocessing done in $O(N)$.
Pros: a very simple data structure. Cons: worse complexity.
- Segment tree - answers each query in $O(\log N)$, preprocessing done in $O(N)$.
Pros: good runtime complexity. Cons: larger amount of code compared to the other data structures.
- Fenwick tree - answers each query in $O(\log N)$, preprocessing done in $O(N \log N)$.
Pros: the shortest code, good runtime complexity. Cons: Fenwick tree can only be used for queries with $L = 1$, so it is not applicable to many problems.

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