Mo's Algorithm
An efficient technique for answering offline range queries using Square Root Decomposition.
Mo's Range Sum
Array (Values)
Current Range Sum
[0, -1]0
Processing Queue (Sorted by Block, then R)
Ready
Controls
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
The Problem: If we answer range queries [L, R] one by one naively, moving from one range to another can take O(N) time, leading to O(N * Q) total time.
The Solution: What if we could re-order the queries so that we don't move our L and R pointers too much?
Mo's Algorithm (named after Mo Tao) does exactly this. It sorts the queries in a specific order so that the total movement of the L and R pointers is minimized to O((N + Q) * \sqrt{N}).
Concept
Square Root Decomposition Strategy:
- Blocking: Divide the array into blocks of size
S = \sqrt{N}. - Query Sorting: Sort the queries based on the block index of their left endpoint
L. If two queries haveLin the same block, sort them by their right endpointR. - Offline Processing: We must know all queries beforehand ("offline") to sort them. We cannot use this for online updates.
How it Works
The visualizer shows the query ranges and the current [currL, currR] window.
- Sort: Queries are re-ordered. Notice how the 'Start' points are grouped by blocks.
- Move R: The Right pointer moves monotonically significantly less often (within each block).
- Move L: The Left pointer stays within the small block range.
- Compute: We transition from the previous query range to the current one by adding/removing elements one by one.
Step-by-Step Breakdown
1. Block Size: Calculate BLOCK_SIZE = sqrt(N).
2. Sort Queries:
- Primary Key: L / BLOCK_SIZE (Ascending)
- Secondary Key: R (Ascending, or Zig-Zag optimization)
3. Process: Initialize currL = 0, currR = -1.
4. Transition: For each query [L, R]:
- while (currL > L) add(--currL)
- while (currR < R) add(++currR)
- while (currL < L) remove(currL++)
- while (currR > R) remove(currR--)
- Store answer.
When to Use
- Offline Range Queries (Sum, Frequency, Mode, Distinct Elements).
- When the array is static (no updates to elements).
- When
NandQare up to10^5.
When NOT to Use
- Online queries (must answer immediately).
- When updates are frequent.
- When a Segment Tree or Fenwick Tree can solve it in
O(log N)(e.g., simple range sum).
How to Identify
"Range queries", "Static Array", "Offline allowed", "Hard to combine ranges (like Mode)".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.