Offline queries
Sometimes all the range queries are known in advance, and they can be answered in any order. When each query asks something hard to summarize, like the number of distinct values in a range, Mo's algorithm shines.
A sliding window over sorted queries
Keep a current window with two ends, plus a running answer that can be adjusted when either end moves by one. Moving an end adds or removes a single element and updates the running answer cheaply.
The trick is the order. Sort the queries cleverly:
- Group queries by which block their left end falls in, using blocks near the square root in size.
- Within a block, sort by the right end.
This ordering keeps the total movement of both ends small across all queries, so the many small adjustments add up to far less work than answering each query from scratch.
Requirements
The method needs an answer that can be incrementally updated as elements enter or leave the window, and it needs all queries up front. When those hold, it is a clean and powerful offline tool.
Key idea
Reorder offline queries by block and right end so a window with incrementally adjustable answer moves only a little overall.