Introduction to MO’s Algorithm Pattern

Mo's Algorithm answers a batch of offline range queries on a static array by sorting the queries so that consecutive queries have nearby endpoints, then sliding a two-pointer window [curL, curR] from one query's range to the next, adding or removing one element at a time instead of recomputing each answer from scratch. Grouping left endpoints into blocks of size about sqrt(N) bounds the total pointer movement across all Q queries to roughly O((N+Q)·sqrt(N)).

Recognize the pattern

• Many queries Q (typically 10⁴–10⁵+) asking for a property of a range [L, R] on one array that never changes between queries (offline, static).
• Extending or shrinking the current range by one index has a cheap incremental update — add(x) / remove(x) in O(1) or O(log N) — e.g. running sum, count of distinct elements, frequency of the mode, XOR.
• You may answer queries out of order and print results back in original order at the end.
• Does NOT fit: point updates interleaved with queries (needs Mo-with-updates, a 3rd dimension), or an add/remove that forces a full O(N) recompute (no incremental structure).

Brute force to optimal

Brute force: for each query scan from L to R and recompute the answer independently. Cost O(Q·N) — with Q = N = 10⁵ that is 10¹⁰ operations, far too slow.

Optimal (Mo's): pick block size B ≈ sqrt(N). Sort queries by (L / B), tie-broken by R (alternate ascending/descending R per block to avoid worst-case re-scans). Maintain a window [curL, curR] and an incrementally-updated answer; move curL and curR one step at a time to reach each query's [L, R] in sorted order.

Complexity, derived from first principles

Split total pointer movement into contributions from L and R separately.

• R pointer: within one block of queries, L only ranges over B consecutive values, and queries in that block are sorted by R, so R moves monotonically across the whole block — at most O(N) movement per block. There are N/B blocks, giving O(N · N/B) = O(N²/B) total R-movement.
• L pointer: within a block, L can move by at most B per query (block width), and there are Q queries, so total L-movement is O(Q·B).
• Total: O(N²/B + Q·B). Minimizing over B by calculus (derivative zero at B = N/√Q) gives B ≈ N/√Q, and substituting back yields O(N·√Q). Using the common simplification B = √N (valid when Q ≈ N, the typical contest case) gives the familiar O((N+Q)·√N).
• Space: O(N) for the array plus O(N) frequency/aux structures plus O(Q) to store and re-sort queries — O(N+Q) total.
• Each single-step add/remove must be O(1) (or O(log N), multiplying the whole bound by log N) or the derivation's O(1)-per-step assumption breaks.

Worked example

Array A = [1, 3, 5, 7, 9, 11, 13, 15] (N = 8). For this trace we pick block size B = 3 purely because it gives clean, easy-to-follow index arithmetic — B is a tunable parameter, not a fixed constant. Note that the shipped Java implementation below instead auto-computes block = (int) Math.sqrt(n), which for n = 8 gives block = 2, not 3; both are valid choices of B, they just differ between this illustration and that specific default. Queries (0-indexed, inclusive): Q1=[2,6], Q2=[0,2], Q3=[3,7].

Sort by block of L (using B=3): Q2 (L=0, block 0), Q1 (L=2, block 0), Q3 (L=3, block 1). Process in that order, sliding [curL,curR] and a running sum:

Total single-element moves here: 3 for init/Q2 (3 adds) + 6 for Q1 (2 removes + 4 adds) + 2 for Q3 (1 remove + 1 add) = 3 + 6 + 2 = 11 moves for 3 queries — far fewer than re-summing every range from scratch once N and Q grow large.

Java implementation

import java.util.*;

class MoQuery {
    int l, r, idx;
    MoQuery(int l, int r, int idx) { this.l = l; this.r = r; this.idx = idx; }
}

public class MoAlgorithm {

    public static long[] answerQueries(int[] a, int[][] queries) {
        int n = a.length, q = queries.length;
        int block = Math.max(1, (int) Math.sqrt(n));
        MoQuery[] qs = new MoQuery[q];
        for (int i = 0; i < q; i++) qs[i] = new MoQuery(queries[i][0], queries[i][1], i);

        Arrays.sort(qs, (x, y) -> {
            int bx = x.l / block, by = y.l / block;
            if (bx != by) return bx - by;
            return (bx % 2 == 0) ? x.r - y.r : y.r - x.r; // alternate direction
        });

        long[] ans = new long[q];
        long curSum = 0; // local accumulator: reset every call, no cross-call state leaks
        int curL = 0, curR = -1;
        for (MoQuery mq : qs) {
            while (curR < mq.r) curSum += a[++curR];
            while (curL > mq.l) curSum += a[--curL];
            while (curR > mq.r) curSum -= a[curR--];
            while (curL < mq.l) curSum -= a[curL++];
            ans[mq.idx] = curSum;
        }
        return ans;
    }
}

Note: curSum is a local variable declared inside answerQueries, so each call starts fresh at 0 — calling this method repeatedly (e.g. across multiple test cases in one process) never leaks state from a prior call. There is no unused freq field here: this example implements range-sum only, so only the state that sum actually needs (curSum) is declared.

Pitfalls

• Forgetting to sort R in alternating direction per block: still asymptotically correct but roughly 2x slower in practice from wasted re-scans at block boundaries.
• Using an add/remove that costs O(N) (e.g. recomputing max via full scan) silently destroys the whole complexity guarantee — it must be O(1)/O(log N).
• Applying Mo's to a mutable array without the update-aware 3D variant — a plain Mo's assumes the array never changes between queries.
• Off-by-one errors in the four while-loops for expanding/shrinking L and R — order matters (expand before shrink) to avoid transient negative-size windows.
• Not restoring answers to original query order before output.
• Keeping query-processing state (like a running answer) in a static field instead of scoping it to the call: if the same class/method runs more than once in a process (multiple test cases, unit tests), leftover state from a previous run silently corrupts the next one. Scope accumulators locally, as in the implementation above.

When to use / when not, and alternatives

• Use when: Q and N are both large (10⁴+), queries are offline, and the metric supports O(1)/O(log N) incremental add/remove (distinct count, mode frequency, sum, XOR).
• Avoid when: queries must be answered online (Mo's requires knowing all queries upfront), or the array is updated between queries (use Mo's with updates, adding a time dimension, O(N^(5/3))) or a segment tree if updates are frequent and metric is associative.
• Vs. Segment Tree / Fenwick Tree: segment trees give O(log N) per query AND support point updates, and work online — strictly more powerful when the query function is associative (sum, min, max). Mo's wins precisely when the function is NOT easily associative/mergeable (e.g. "count distinct in range") but IS easily updated one element at a time.
• Vs. Sparse Table: sparse tables answer idempotent range queries (min/max) in O(1) with O(N log N) preprocessing but need updates never to happen and the function to be idempotent; Mo's has no such idempotency restriction.

Takeaways

• Mo's Algorithm trades an ordering trick (sort by sqrt-block of L, then R) for near-linear total pointer movement across all queries.
• The O((N+Q)√N) bound falls out of splitting movement into an R-term (O(N²/B)) and an L-term (O(QB)) and balancing them via B ≈ N/√Q.
• It only works when queries are offline and the range metric has a cheap single-element add/remove.
• Prefer a segment tree instead whenever the metric is associative and updates or online queries are required.

Recall: Why does sorting queries by block of L, then alternating the sort direction of R per block, bound the total movement of the R pointer to O(N·N/B) instead of O(Q·N)?

Synthesized from competitive-programming references on Mo's Algorithm and Square Root Decomposition; complexity derivation is original to this page.