Mo's Algorithm
Offline range-query ordering that trades sorting plus add/remove operations for fast answers on static arrays.
Mo's Algorithm
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Mo's algorithm is an offline range-query technique for static arrays. It does not invent a new query formula. It reorders the queries so one maintained interval can be reused efficiently from one query to the next.
Problem-Driven Motivation
This technique appears when a problem has:
a static array,
many subarray queries,
an answer that is awkward for Fenwick trees or segment trees,
but a statistic that is easy to update when one element enters or leaves the current interval.
The classic example is distinct values in subarrays. A segment tree does not naturally support ``how many values have positive frequency'' with easy merges. But if I already know the current interval, adding or removing one endpoint is trivial.
Recognition Pattern
Mo's algorithm is usually worth considering when:
the array is static or nearly static,
offline processing is allowed,
the answer can be maintained by symmetric
add(index)andremove(index)operations,\(O((n+q)\sqrt{n})\) is acceptable and a cleaner online \(\log n\) structure is not obvious.
Typical signals are:
distinct values,
frequency-score queries,
range statistics with local add/remove logic,
tree versions after Euler tour reduction.
Derivation
If I answer queries in arbitrary order, the maintained interval may jump wildly, so the total number of endpoint moves is too large. The only real freedom in an offline problem is the order of the queries, so Mo's algorithm spends that freedom to reduce pointer movement.
Split indices into blocks of size about \(\sqrt{n}\). Sort queries by:
block of the left endpoint,
then by right endpoint, often alternating direction per block to reduce movement in practice.
After sorting, maintain one active interval \([curL, curR]\). To reach the next query \([l,r]\), move the endpoints one step at a time and call only:
add(index),remove(index).The entire method depends on one invariant:
After every single pointer move, the maintained state matches the current active interval exactly.
Worked Problem
Problem.
For each query \([l,r]\), count how many distinct values appear in \(a[l \dots r]\).
Why naive fails.
Scanning each interval independently is \(O(nq)\), which is too slow at \(n,q \le 2 \cdot 10^5\).
Why prefix methods are awkward.
Distinct-count is not an additive statistic. There is no simple formula that subtracts two prefix answers.
Mo invariant.
Maintain:
a frequency array \(\texttt{freq[value]}\),
one integer \(\texttt{distinct}\).
Then:
on add of value \(x\), if \(\texttt{freq[x]}\) becomes \(1\), increment \(\texttt{distinct}\),
on remove of value \(x\), if \(\texttt{freq[x]}\) becomes \(0\), decrement \(\texttt{distinct}\).
Final algorithm.
coordinate-compress values if needed,
sort queries in Mo order,
move the current interval toward each query,
record \(\texttt{distinct}\) when the interval matches.
Implementation Reasoning
The logic of add and remove matters more than the sorting comparator. If those two functions are not perfect inverses of each other, Mo's algorithm quietly returns nonsense.
Practical implementation choices:
compress large values first, or the frequency array becomes impossible to allocate,
use alternating right-endpoint order inside each block for better constants,
keep intervals consistently inclusive or half-open; mixing the two is a common bug source.
The code below is intentionally the classic distinct-values version because it demonstrates the invariant cleanly.
Correctness Intuition
Reordering queries does not change their meaning. It only changes how much work is reused between them. As long as each endpoint move updates the maintained state correctly, the final state after all moves equals the answer for the new interval.
Complexity Analysis
With block size about \(\sqrt{n}\) and \(O(1)\) add/remove:
sorting: \(O(q \log q)\),
total interval movement: about \(O((n+q)\sqrt{n})\),
memory: usually \(O(n)\) or \(O(\text{value range after compression})\).
Common Pitfalls
Forgetting that the whole method is offline.
Writing
addandremovethat are not exact inverses.Using raw values without compression.
Choosing Mo's algorithm when a simpler online structure already solves the problem more directly.
Variants and Failure Modes
Mo with updates adds a time dimension and is significantly more fragile.
Tree Mo first reduces the tree to an Euler-tour order.
Hilbert-order sorting often improves constants.
If add/remove are not cheap, Mo's ordering alone does not save the solution.
Practice Problems
Distinct values on subarrays.
Frequency-score range queries.
Offline array or tree queries with local add/remove maintenance.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct Query {
int l;
int r;
int idx;
};
// Example application: count distinct values on many static subarrays.
vector<int> mos_distinct(const vector<int>& values, vector<Query> queries) {
int n = (int)values.size();
if (n == 0) return vector<int>(queries.size(), 0);
int block = max(1, (int)sqrt(n));
sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
int block_a = a.l / block;
int block_b = b.l / block;
if (block_a != block_b) return block_a < block_b;
if (block_a & 1) return a.r > b.r;
return a.r < b.r;
});
int max_value = 0;
for (int x : values) max_value = max(max_value, x);
vector<int> freq(max_value + 1, 0);
vector<int> answers(queries.size(), 0);
int current_left = 0, current_right = -1;
int distinct = 0;
auto add = [&](int index) {
if (++freq[values[index]] == 1) ++distinct;
};
auto remove = [&](int index) {
if (--freq[values[index]] == 0) --distinct;
};
for (const Query& query : queries) {
while (current_left > query.l) add(--current_left);
while (current_right < query.r) add(++current_right);
while (current_left < query.l) remove(current_left++);
while (current_right > query.r) remove(current_right--);
answers[query.idx] = distinct;
}
return answers;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.