Range Query Processing (prefix, trees)

Range queries ask about contiguous segments—sum, min, xor—with or without updates. Segment trees, Fenwick trees, and sqrt decomposition are the standard toolkit.

Why this shows up in the real world

Time-series DBs aggregate windows. Genomics slides windows along chromosomes.

Core idea (explained for students)

Static sum → prefix difference. Static min with updates → segment tree. Many updates + range assign → lazy propagation.

Try this in Python

def range_sum_prefix(pref: list[int], l: int, r: int) -> int:
    return pref[r] - pref[l]


pref = [0, 2, 5, 9]
print(range_sum_prefix(pref, 0, 3))

Common mistakes

• Fenwick for min without careful ordering—classic misuse; use segment tree instead.
• Off-by-one mixing inclusive r with half-open slices.

Key takeaways

• Draw half-open intervals [l, r) consistently in code and proofs.
• Mo's algorithm when updates are absent but many offline range queries exist.