Mo's Algorithm, in depth: answering offline range queries in O((n + q) sqrt n) by reordering them

The contract: a window you can grow and shrink

Mo's algorithm knows nothing about your query. It maintains a current window [cur_l, cur_r] and a data structure describing it, and it needs exactly three things from you:

1. add(i): include element i in the window and update the answer state.
2. remove(i): exclude element i and update the answer state.
3. answer(): report the answer for the current window.

For distinct counting the state is a frequency array cnt plus a counter distinct. Adding a value whose count goes from 0 to 1 increments distinct; removing a value whose count drops to 0 decrements it. Both are O(1). For any query of the form [l, r], moving from the previous window to the new one costs |l - cur_l| + |r - cur_r| calls. The whole problem becomes: order the queries so the total pointer travel is small.

The order depends on every query, so the technique is offline: if each answer is needed before the next query is revealed (for example forced decoding such as l = (l' + last_answer) mod n), Mo's algorithm does not apply.

The cost model and the block size

Split the index range into blocks of size B. Sort queries by the block containing l, and within one block by r. Now count pointer moves.

• Right pointer. Within a block, r only increases, so it travels at most n positions per block. There are n / B blocks, so the right pointer moves at most n x n / B in total, plus up to n when jumping between blocks.
• Left pointer. Inside one block, l stays within a span of B positions, so each query moves it at most B (plus at most 2B when changing block). Over q queries that is at most q x B.

Total cost is about n^2 / B + qB. Minimise by setting the two terms equal: B = n / sqrt(q), which gives O(n sqrt q). When q is close to n, B = sqrt(n) and the cost is O(n sqrt n). Block sizes within a factor of two of n / sqrt(q) perform about the same; just avoid B = sqrt(n) when q is far smaller than n, because the right-pointer term then dominates.

Concretely, for n = q = 200,000 the bound is about 2 x 200,000 x 447, or 1.8 x 10^8 O(1) updates. In C++ with an int array for cnt that runs in well under a second. In pure Python it is far too slow; use C++, Rust, Java or a compiled extension for the hot loop.

The worked example

Take a = [1, 2, 1, 3, 2, 2, 4, 1] (n = 8, zero-indexed) and five inclusive queries: q0 = [0,4], q1 = [2,6], q2 = [5,7], q3 = [1,3], q4 = [0,7]. Use B = 3, so l = 0..2 is block 0 and l = 3..5 is block 1. Queries q0, q1, q3 and q4 have l in block 0; q2 has l = 5, block 1. Sorting block 0 by r ascending gives q3 (r = 3), q0 (r = 4), q1 (r = 6), q4 (r = 7), then q2.

That is 19 add/remove calls against 24 element visits for naive rescanning. The saving is small at n = 8; it grows with n because the naive cost is the sum of query lengths (up to nq), while Mo's cost is bounded by n^2 / B + qB. Answers are written back by original index: q0..q4 = 3, 4, 3, 3, 4.

Reference implementation

The Python below is the readable version; it was run on the example above and reproduces the table. Note the loop order: the two loops that grow the window run before the two that shrink it. If you shrink first, cur_l can pass cur_r + 1, the window becomes negative, and remove is called on elements that were never added, driving counts below zero.

def mo_distinct(a, queries):
    n, q = len(a), len(queries)
    B = max(1, int(n / max(1, q) ** 0.5))
    def key(i):
        l, r = queries[i]
        blk = l // B
        return (blk, r if blk % 2 == 0 else -r)   # odd-even trick
    order = sorted(range(q), key=key)

    cnt = [0] * (max(a) + 1)       # compress values first if they are large
    distinct = 0
    cur_l, cur_r = 0, -1
    ans = [0] * q
    for qi in order:
        l, r = queries[qi]
        while cur_r < r:                      # grow right
            cur_r += 1; x = a[cur_r]; cnt[x] += 1; distinct += cnt[x] == 1
        while cur_l > l:                      # grow left
            cur_l -= 1; x = a[cur_l]; cnt[x] += 1; distinct += cnt[x] == 1
        while cur_r > r:                      # shrink right
            x = a[cur_r]; cnt[x] -= 1; distinct -= cnt[x] == 0; cur_r -= 1
        while cur_l < l:                      # shrink left
            x = a[cur_l]; cnt[x] -= 1; distinct -= cnt[x] == 0; cur_l += 1
        ans[qi] = distinct
    return ans

The odd-even trick in key sorts r ascending in even blocks and descending in odd blocks. Without it, the right pointer sweeps to the end of the array in one block and then flies all the way back to the start for the next. With it, the pointer zig-zags, which often cuts right-pointer travel substantially. It changes no answers, only the constant.

Two production details matter more than micro-optimisation. First, coordinate-compress values to 0..k-1 so cnt is a dense array rather than a hash map; hashing in the inner loop can cost more than the algorithm itself. Second, sort query indices once with a precomputed integer key. In C++ the same four loops collapse to one line each, for example while (curR < r) distinct += (++cnt[a[++curR]] == 1);.

Better orders: Hilbert curve sorting

Think of each query as a point (l, r). Mo's order is a path through those points, and total pointer movement is the Manhattan length of that path. Block sorting is one good path; sorting by each point's index along a Hilbert curve of side 2^k at least n is another. The curve preserves locality in both coordinates, so the bound stays O(n sqrt q) while the constant is often smaller, especially when q is much smaller than n. The index costs about 20 lines of bit manipulation, computed once per query; benchmark both orders on your real query distribution.

Mo with updates

If the input interleaves point updates (a[pos] = value) with queries, add a third dimension: time, the number of updates applied before the query. Each query becomes (l, r, t). Keep a time pointer alongside the two index pointers. Moving time forward applies an update: if the position lies inside the current window, remove the old value and add the new one; then swap the stored old and new values so moving backward undoes it with the same code.

Sort by (l / B, r / B, t) with B about n^(2/3). The left and right pointers move O(qB) each, and the time pointer moves at most U (the number of updates) per pair of blocks, with (n / B)^2 pairs. With q and U both of order n this gives O(n^(5/3)), slower than plain Mo but still far better than O(nq) for n around 10^5.

Mo on trees

For path queries on a tree (distinct colours on the path from u to v, for example), flatten the tree with an Euler tour that records each node twice: st[v] when entering and en[v] when leaving. In the tour sequence, a node that appears twice inside a range is not on the path; a node that appears once is. So instead of add and remove, each position toggles its node: if the node is currently in the window, remove it, otherwise add it.

• Order u and v so st[u] <= st[v].
• If u is the lowest common ancestor of v, the path is exactly the range [st[u], st[v]].
• Otherwise the range [en[u], st[v]] covers the path except the LCA itself; toggle the LCA in, read the answer, and toggle it out again.

The sequence has length 2n, so the bound is the same as plain Mo with n doubled. Computing the LCA is a separate preprocessing step (binary lifting or Euler tour plus range minimum); see the lowest common ancestor guide for the options.

Rollback Mo: when you cannot remove

Some window states support cheap insertion but not deletion. The maximum value is the classic example: adding updates the maximum in O(1), but removing the current maximum requires knowing the second largest. Rollback Mo (also called add-only Mo) avoids removal entirely.

1. Queries that lie entirely inside one block are answered by brute force in O(B) each.
2. For every other query, group by the block of l. For a block ending at position E, reset the state to empty with the right pointer at E. Process that block's queries by increasing r, so the right pointer only adds.
3. For each query, extend the left pointer from E + 1 down to l with adds, save the answer, then undo those left-side adds from a stack of saved values, restoring the state to 'window [E + 1, r]'.

Undoing restores saved snapshots, so you never compute a state without an element. Complexity stays O(n sqrt q).

When to use Mo's algorithm, and when not to

Mo's algorithm is the general fallback: with an O(1) per-element update it guarantees a sub-quadratic bound. If a logarithmic structure exists for your query, prefer it. For the asymptotic reasoning behind these comparisons, see big-O analysis.

Failure modes

• Shrinking before growing. Counts go negative or out of bounds. Always grow both ends first.
• Hash map state. Correct but several times slower; compress values to a dense range.
• Wrong block size for skewed q. With q much smaller than n, B = sqrt(n) makes the right pointer dominate; use n / sqrt(q).
• Expensive add or remove. If an update costs O(log n), the total becomes O(n sqrt q log n); check that it still fits the time limit, or find an O(1) state.
• Inclusive versus half-open ranges. Mixing [l, r] and [l, r) shifts every answer by one element; normalise on input.

What to do next

1. Implement the distinct-count version above, verify it against brute force on random arrays of size 50 with 200 random queries, then time it at n = q = 200,000 in a compiled language.
2. Add the odd-even trick and then a Hilbert order, and measure the change in total pointer moves on your workload.
3. Write the add, remove and answer functions for 'number of values that appear exactly twice in the range' and check them with the same brute-force harness.
4. Extend to Mo with updates by adding the time pointer, and test it against a naive solver that replays updates.
5. Implement Mo on trees using an Euler tour and LCA, and test path queries on small random trees.
6. Before using Mo in a real problem, ask whether a segment tree, Fenwick tree or offline sweep already solves it in O(log n) per query.