Range Query

A range query asks for information about a contiguous section of an array or sequence.

Examples include the sum, minimum, maximum, greatest common divisor, or count over indexes left through right.

Core Idea

Answering one range query by scanning the range may be fine. Answering many range queries by scanning each range can be too slow.

Range query structures trade preprocessing or update complexity for faster repeated queries.

Python Example

def range_sum_slow(values, left, right):
    total = 0
    for i in range(left, right + 1):
        total += values[i]
    return total

This direct version costs O(right - left + 1) per query.

Common Confusions

The best structure depends on whether the array changes. A fixed array, point updates, and range updates lead to different choices.

The operation also matters. Sum, minimum, maximum, and GCD do not all support the same shortcuts.

When To Use It

Use range-query thinking when many questions ask about intervals of the same sequence and repeated scanning would be too slow.