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.

Function Contract

range_sum_slow(values, left, right) expects numeric values and valid inclusive indexes left and right.

It returns the direct sum of that range by scanning every position. The function is intentionally simple so the cost of repeated range queries is visible.

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.

Why Direct Scanning Fails

If there are q queries and each query may scan up to n elements, the total time can become O(nq). That is often too slow when both n and q are large.

Range query structures reduce repeated scanning by storing reusable information.

Choosing a Structure

The right structure depends on the operations:

• Fixed array and range sums: prefix sum.
• Point updates and prefix/range sums: Fenwick tree.
• Flexible range queries and updates: segment tree.
• Range updates with range queries: segment tree with lazy propagation.
• Fixed array and many idempotent queries such as minimum: sparse table.

The operation matters because not every summary can be subtracted or combined the same way.

Complexity Goal

The usual goal is to move from linear work per query to logarithmic or constant work per query, after some preprocessing.

Reading the Constraints

Range query problems are often decided by constraints. If there are only a few queries, direct scanning may pass. If there are hundreds of thousands of queries, the preprocessing structure often becomes necessary.

Also check whether updates are mixed with queries. Static and dynamic versions can require completely different tools.

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.

Another common mistake is learning one range structure and using it everywhere. The simplest structure that matches the constraints is usually best.

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.

Do not build a complex structure for one or two small queries. A direct scan may be clearer and fast enough.

The Main Point

Range-query structures exist because repeated interval scans can become too slow. The right structure depends on queries, updates, and operation type.