Introduction to Mo's Algorithm
Understanding the problem of Offline Range Queries and the intuition behind Square Root Decomposition.
Query Processing Order
Current Move Cost: 0
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
We are given an array and many queries `(L, R)` asking for the sum (or other property) in that range.
If we answer queries as they come, our pointers might jump wildly from the beginning to the end of the array, wasting time. What if we could re-arrange the queries to "smooth out" the movement?
Concept
Sorting Queries:
- Divide indices into buckets of size `sqrt(N)`.
- Sort queries by their **Left Bucket Index**.
- If in the same bucket, sort by **Right Index**.
This simple trick ensures `L` moves slowly (within a bucket) and `R` sweeps back and forth efficiently.
How it Works
The visualizer compares Naive Order vs Mo's Order.
- Naive: The pointers (blue bars) jump erratically across the array. Total distance is huge.
- Mo's: The pointers move in a controlled snake-like pattern. Total distance is minimized.
Step-by-Step Breakdown
1. Identify the block size `B = sqrt(N)`.
2. Assign each query a `block_id = L / B`.
3. Sort queries: Primary logic `block_id`, Secondary logic `R`.
4. Process sequentially.
When to Use
- Offline Range Queries.
- You can't use Segment Tree (e.g., computing Mode frequency).
When NOT to Use
- Online queries (must answer immediately).
- Updates to array values (Mo's is static usually).
How to Identify
"Range queries", "Static Array", "Offline processing allowed".
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.