Fast Queries (Optimizing Multiple Queries)

Fast queries after preprocessing—prefix sums, sparse tables, segment trees—turn each query from scanning data to touching a logarithmic or constant number of nodes.

Why this shows up in the real world

Maps tile pyramids so pan/zoom queries stay smooth. Metrics backends downsample with pre-aggregates.

Core idea (explained for students)

Choose structure by query type: static range sum → prefix array; min with updates → segment tree or Fenwick with coordinate compression.

Try this in Python

def build_prefix(a: list[int]) -> list[int]:
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p


def range_sum(p: list[int], l: int, r: int) -> int:
    return p[r + 1] - p[l]


p = build_prefix([3, 1, 4, 1, 5])
print(range_sum(p, 1, 3))

Common mistakes

• Building O(n) structure for Q=1 query—wasteful.
• Off-by-one on inclusive/exclusive prefix boundaries.

Key takeaways

• Compare build cost + query cost vs brute force for your Q and n.
• Write index conventions once in a comment block.