Algorithms / Offline Sorting Sweep
Least You Need to Know: Offline Sorting, Event Sweeps, and Ordered Processing
Offline processing sorts updates, queries, or events by a key so work can be done in one monotone sweep. The key insight is to answer many questions by **maintaining a moving frontier** rather than restarting from scratch for each query.
The least you need to know
- Offline algorithms may reorder queries because all input is known in advance.
- Sorting by a key often turns repeated scanning into one sweep.
- Events must be processed in a carefully chosen tie-break order.
- Fenwick trees frequently pair with offline sorting to maintain active information.
- Offline processing is different from online algorithms that must answer immediately.
Key notation
event
update or query processed in the sweep order
sweep key
sorted coordinate or threshold used to order events
active set
information currently maintained while sweeping
Tiny worked example
- Suppose queries ask how many intervals start before position `x`.
- Sort interval starts and queries by position.
- Sweep left to right, adding intervals as they become active.
- Each query is answered from the current maintained state instead of rescanning all intervals.
Common mistakes
- Offline processing is only allowed when reordering queries does not violate the problem contract.
- Tie-breaking can matter: updates at position `x` may need to run before queries at `x` or after them depending on inclusivity.
- A sweep needs a maintained state, not just a sorted list.
How to recognize this kind of problem
- All queries are known beforehand and can be reordered.
- A threshold or coordinate sorting key naturally orders the work.
- You want one pass with incremental maintenance rather than repeated full scans.