Batch Query Processing (Handling Large Queries Efficiently)

Batching groups many queries so shared preprocessing pays off once—Mo's algorithm on arrays, offline sorting of queries with DSU, or building a segment tree then answering O(log n) each.

Why this shows up in the real world

Analytics dashboards pre-aggregate hourly buckets instead of scanning raw rows per widget. Game engines batch ray tests against the same BVH.

Core idea (explained for students)

Pattern: sort queries by a key (time, block index), maintain a structure that supports add/remove as the sweep line moves, answer each query when its window is ready.

Try this in Python

def batch_prefix_answers(a: list[int], ranges: list[tuple[int, int]]) -> list[int]:
    pref = [0]
    for x in a:
        pref.append(pref[-1] + x)
    return [pref[r + 1] - pref[l] for l, r in ranges]


print(batch_prefix_answers([1, 2, 3, 4], [(0, 2), (1, 3)]))

Common mistakes

• Forgetting to sort queries in the same order the offline algorithm assumes.
• O(Q²) hidden when each batch rebuilds from scratch unnecessarily.

Key takeaways

• Name the sweep invariant explicitly in comments.
• Compare batch vs online: sometimes a Fenwick tree update beats fancy offline.