In a range query, our task is to calculate a value based on a subarray of an array. Typical range queries are:
- : calculate the sum of values in range
- : find the minimum value in range
- : find the maximum value in range
These queries are usually in time, so with queries, it becomes time.
We can optimize this time using various Data Structures.
Range Sum query
A sum query is very straightforward, just use a Prefix Array in time.
Range Minimum Query (Query)
For a range minimum query, there are several methods.
Approaches that only work on static arrays:
Approaches that allow modifications to the array between answering queries: