Range Minimum Query¶
You are given an array
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.
- Sqrt-decomposition - answers each query in
- Segment tree - answers each query in
- Fenwick tree - answers each query in
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.
- Sparse Table - answers each query in
- Sqrt Tree - answers queries in
- Disjoint Set Union / Arpa's Trick - answers queries in
- Cartesian Tree and Farach-Colton and Bender algorithm - answers queries in
Note: Preprocessing is the preliminary processing of the given array by building the corresponding data structure for it.