Sign in to watch this lesson
Advanced - Data Structures and Range Queries · 4:03
Mo's Algorithm
When every range query is known in advance and the answer is easy to update one element at a time but impossible to merge (distinct values, the top frequency, equal pairs), Mo's algorithm answers them all by moving a single window. Sorting queries by (l / S, r) with S around √n, and snaking r through alternate strips, keeps the total movement at O((n + Q)√n) add/remove calls. The window must expand before it shrinks, the block size should be a constant, and answers go back to their original indices.
You will learn
- Recognise queries that suit Mo's algorithm: cheap add/remove of one element, no way to merge two halves, all queries known in advance
- Implement Mo's ordering by (l / S, r) with odd-even strips and maintain a window with add and remove
- Derive the O((n + Q)·√n) bound from the movement of the two pointers and choose S accordingly
- Avoid the classic bugs: shrinking before expanding, a non-constant block size, and answers stored out of order