Range Query

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: