You have an array and a big batch of range queries — “what’s the answer on [l, r]?” — that you can answer offline (all at once, in any order). Mo’s algorithm keeps a single window with two pointers and slides them from one query’s range to the next, using cheap add and remove steps at the ends. If you processed the queries in their given order, the pointers would thrash back and forth for O(q·n) total movement. The trick is the order: sort queries by the √n-sized block of their left endpoint (then by right endpoint), and the total movement collapses to O((n+q)·√n). Watch reordering slash the pointer movement.
O((n+q)·√n) total · offline queries only · sort by √n block of L, then by R
offline
All queries are known up front and may be answered in any order.
window
One current range [curL, curR] with an incrementally maintained answer.
add / remove
Extend or shrink the window by one element at an end — a cheap O(1) update.
Mo's order
Sort queries by (block of L = ⌊L/√n⌋, then R). This bounds total pointer movement.
mo.js — the same queries, a smarter order
Ready
Eight range queries over a 16-element array. Sorted in Mo’s order, we keep one window and slide its ends to each query in turn. Step to process the next query and count the add/remove moves.
0/8
queries done
0
total moves
99
naive order
How it works
The magic is entirely in the sort key. Group the queries by which √n-sized block their left endpoint falls in. Within a block, sort by the right endpoint. Now two things are bounded. The left pointer only ever moves within a block between consecutive queries, so it travels at most √n per query — O(q·√n) overall. The right pointer, because queries within a block are sorted by R, marches mostly forward within each block and resets at most once per block, for O(n·√n / √n) = O(n·√n)… more precisely O(n·√n) total across all blocks. Add them and the whole batch costs O((n+q)·√n) pointer moves, each a constant-time add/remove — dramatically less than answering each query from scratch.
1
Collect queries offline
Read all q range queries first. Mo’s algorithm needs them up front because it will answer them in a rearranged order.
2
Sort by (block of L, then R)
Choose block size ≈ √n. Sort queries by ⌊L/√n⌋, breaking ties by R. This ordering is what bounds the total pointer travel.
3
Slide the window
Maintain one window [curL, curR] and its answer. For each query, move the two ends to the query’s l and r with add/remove steps, updating the running answer in O(1) each.
✓
O((n+q)·√n) total
The sorted order keeps the left pointer within a block (√n per query) and the right pointer mostly monotic within a block, so all the sliding sums to O((n+q)·√n) — then map answers back to original query order.
1. What does Mo’s algorithm require of the queries?
Mo’s algorithm rearranges the queries to minimize pointer movement, so it must know all of them up front and be free to answer them in a different order — that is, they must be offline.
2. What is the key ordering Mo’s algorithm sorts queries by?
Sort by (⌊L/√n⌋, R). Grouping by the left endpoint’s √n block bounds left-pointer movement to √n per query, and sorting by R within a block keeps the right pointer mostly monotonic — together giving O((n+q)·√n).
3. What is Mo’s algorithm’s total time for q queries on an n-element array?
The clever sort bounds total pointer movement to O((n+q)·√n), each move an O(1) add/remove — far better than the O(q·n) of answering each query by scanning its range.
FAQ
What is Mo's algorithm?
An offline technique for answering many range queries on a static array. It keeps one window with two pointers and a running answer, and processes queries sorted by (√n block of L, then R) so pointer movement between queries is cheap — O((n+q)·√n) total, far better than answering each independently.
Why does the √n block ordering make it fast?
Grouping by the √n block of L keeps the left pointer within a block (≤√n per query → O(q·√n)). Sorting within a block by R keeps the right pointer mostly forward, resetting once per block (→ O(n·√n)). The sum is O((n+q)·√n).
What problems is Mo's algorithm used for?
Range queries whose answer updates incrementally as elements enter/leave the window: distinct count in a range, most-frequent element, sum of squared frequencies, and many frequency/mode questions. It needs O(1)-ish add/remove updates and a static array.
What are the limitations of Mo's algorithm?
It’s offline-only, basic version needs a static array (a harder O(n^(5/3)) variant allows updates), and requires cheap add/remove answer maintenance. When you need online queries or frequent updates, a segment tree or similar is usually better.