Offline Query Processing (Sort queries, sweep, DSU)

Offline means you see all queries before answering—sort them, sweep with a DSU, or divide-and-conquer on query time. Online algorithms must commit without future knowledge.

Why this shows up in the real world

MapReduce batches jobs with full input visibility. Static analysis may traverse the whole call graph before reporting.

Core idea (explained for students)

Sort queries by right endpoint, extend a Fenwick tree as you sweep, answer when the active prefix matches each query's left bound—classic pattern.

Try this in Python

def offline_max_in_windows(values: list[int], windows: list[tuple[int, int]]) -> list[int]:
    ans = []
    for l, r in sorted(windows, key=lambda w: w[1]):
        ans.append(max(values[l : r + 1]))
    return ans


print(offline_max_in_windows([3, 1, 4, 1, 5], [(0, 2), (1, 4)]))

Common mistakes

• Applying offline tricks to strictly online streams without buffering policy.
• Wrong comparator when queries share endpoints—tie-break carefully.

Key takeaways

• If the statement allows buffering, ask whether offline simplification is intended.
• Document query ordering assumptions in README-level comments.