# Range Query

In a range query, our task is to calculate a value based on a subarray of an array. Typical range queries are:

- $sum_{q}(a,b)$: calculate the sum of values in range $[a,b]$
- $min_{q}(a,b)$: find the minimum value in range $[a,b]$
- $max_{q}(a,b)$: find the maximum value in range $[a,b]$

These queries are usually in $O(n)$ time, so with $q$ queries, it becomes $O(nq)$ 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 $O(n)$ 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:

- Segment Tree
- Fenwick Tree
- Square Root Decomposition (idk what this is)