Range Query

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

• $su{m}_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:

• Sparse Table

Approaches that allow modifications to the array between answering queries:

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