Skip to content

Mo’s Algorithm

Mo’s algorithm answers offline range queries on a static array by reordering queries in \(\sqrt{n}\)-sized blocks on the left endpoint so that moving the current \([L,R]\) window is cheap to update.

Typical use

  • Count distinct values in each range, number of inversions-like statistics, etc.—when you can add one position and remove another in \(O(1)\) or \(O(\log n)\) while maintaining an aggregate.

Ordering

Sort queries by (block(L), R) with alternating R direction per block (Hilbert order is a modern alternative for fewer cache misses).

Complexity

If add/remove is \(O(1)\): \(O((n + q) \sqrt{n})\) for \(q\) queries on length \(n\). With \(O(\log n)\) updates, multiply accordingly.

Sketch

// Sort queries by (L/blockSize, R) with parity trick on R within blocks
// Maintain [curL, curR] and current answer; expand/shrink one index at a time