C++ Reference: range_minimum_query
This documentation is automatically generated.We use the notation min(arr, i, j) for the minimum arr[x] such that i <= x and x < j. Range Minimum Query (RMQ) is a data structure preprocessing an array arr so that querying min(arr, i, j) takes O(1) time. The preprocessing takes O(n*log(n)) time and memory.
Note: There exists an O(n) preprocessing algorithm, but it is considerably more involved and the hidden constants behind it are much higher.
The algorithms are well explained in Wikipedia: https://en.wikipedia.org/wiki/Range_minimum_query.
Implementation: The idea is to cache every min(arr, i, j) where j - i is a power of two, i.e. j = i + 2^k for some k. Provided this information, we can answer all queries in O(1): given a pair (i, j) find the maximum k such that i + 2^k < j and note that std::min(min(arr, i, i+2^k), min(arr, j-2^k, j)) = min(arr, i, j).