Mo's Algorithm (Offline Range Queries on Arrays)

Mo’s algorithm answers offline range queries on a static array in O((n+q)√n) by reordering queries into blocks and moving two pointers with add/remove.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Great when updates are absent and memory is tight vs segtree—need O(1) add/remove for the aggregate.

Try this in Python

# Mo's: sort queries by (l//B, r) with B ~ int(n**0.5); move L,R adding/removing.
B = 3
queries = [(0, 2), (1, 4)]
print(sorted(queries, key=lambda q: (q[0] // B, q[1])))

Common mistakes

• Using Mo’s with updates (use Mo’s with modifications or segtree).
• Wrong block size (should be ~√n).

Key takeaways

• Sort queries by (block(l), r) with odd-even trick on r.
• Maintain frequency array for “distinct count” queries.