Mo's Algorithm
Reorder offline range queries so a moving window can answer them with small pointer adjustments instead of rebuilding from scratch.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
Q0 [1, 5]
block 0, right 5
Q1 [2, 7]
block 0, right 7
Q2 [0, 3]
block 0, right 3
Pointer movement for Q1 [2, 7]
L: 1 -> 2, R: 5 -> 7
Offline queries, cheap incremental maintenance
Mo's algorithm reorders queries so the current range changes only a little from one query to the next. The savings come from pointer movement, not a fancy merge tree.
Family
Range queries
Static and dynamic range aggregates via indexed trees, segment trees, and precomputed tables.
Builds on
1 topic
Read these first if you want the surrounding context.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
You have many range queries on a static array, but the merge operation is awkward enough that prefix sums are impossible and segment trees are inconvenient.
Core idea
Sort the queries in block order, usually by:
L / blockSize- then
R
Now sweep through the queries with a current range [curL, curR]. For each new query, adjust the endpoints a little and update the answer incrementally.
The algorithm wins by making consecutive queries similar.
Why it matters
Mo’s algorithm is the standard answer when:
- queries are offline
- updates are absent or heavily restricted
- you can add/remove one element from the current range quickly
- no nice associative segment-tree merge is available
Complexity
Classic ordering gives about:
plus the cost of your add/remove operations.
Key takeaways
- Mo’s algorithm is about query ordering, not a new data structure
- It is useful when local add/remove updates are easy but direct merges are hard
- Offline constraints are essential: you must know all queries beforehand
- This is rare advanced range-query material, but extremely high-signal for contest-style problems
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Powerful Array | 🔴 Hard | Classic Mo’s ordering |
| Distinct Values Queries | 🔴 Hard | Offline range distinct counts |
| Mo’s references | 🔴 Hard | Range reordering logic |
Relation to other topics
- Prefix Sum is what you would use if the query were additive and simple
- Segment Tree is the online merge-friendly alternative
- DSU Rollback is another offline trick where time gets reordered or rewound strategically
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
DSU Rollback
Add an undo stack to Union-Find so merges can be reversed during offline divide-and-conquer or time-travel style processing.
Persistent Segment Tree
Keep every version of a segment tree by path-copying only the changed nodes.
Segment Tree
Answer range queries and point updates in O(log n). Segment trees are the go-to structure for range sum, range min, and similar problems.
More from Range queries
Stay in the same family when you want parallel variations of the same mental model.
Prefix Sum
Precompute cumulative totals so any range sum becomes one subtraction. Prefix sums are the first serious range-query idea everyone should know.
Difference Array
Apply many range updates in O(1) each, then rebuild the final values with one prefix pass. Difference arrays are the update-side twin of prefix sums.
Fenwick Tree (Binary Indexed Tree)
Maintain prefix sums with O(log n) updates and queries using one tiny bit trick. Fenwick trees are the lightest dynamic range-query structure worth knowing.
Li Chao Tree
Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
Range-query toolkit
Start with static prefix tricks, then move into offline, persistent, dynamic, and precomputed range-query structures.
Offline toolkit
See how reordering queries, rolling back state, and preserving versions can replace online complexity.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.