↩ back to Array-Backed Trees

Mo's Algorithm

Every other entry in this category answers range queries online — one query arrives, you answer it immediately, then the next one arrives. Mo's Algorithm is for a different shape of problem: a whole batch of m range queries over a fixed array, all known in advance, that you're free to answer in any order before handing the results back matched to their original request. That freedom is the entire trick. Reorder the queries by which √n-sized block their left end falls in, then by their right end, and a single sliding window [curL, curR] can walk from one query's range to the next by adding or removing only one array element at a time — no tree, no per-range recombination, and critically, no requirement that the running answer be computable by merging two sub-answers the way a segment tree needs. That last point is what makes this a genuinely new tool rather than a slower segment tree: "how many distinct values appear in [L, R]" has no efficient merge — knowing the distinct count of the left half and the right half separately doesn't tell you how many values they share — but it has a trivial single-element update: track each value's frequency, and a count goes from present to absent (or back) only when its frequency crosses zero.

Try it

The array below has 12 values, indexed 0 through 11, split into blocks of size 4 (⌈√12⌉ = 4, tick marks show the block edges). The four queries below it ask "how many distinct values appear in this range?", listed in the order they arrived. Leave the checkbox on and press Load, then Step through — watch the highlighted window slide from query to query, one element at a time, and the pointer-move counter climb. Then untick the checkbox, reload, and step through the exact same four queries answered in their original arrival order instead of block-sorted: same final answers, far more pointer moves to get there.

Why it works

On the default array [1, 2, 1, 3, 2, 4, 1, 3, 3, 2, 4, 1] with queries arriving as Q0=[2,9], Q1=[0,3], Q2=[5,11], Q3=[1,6]: block 0 covers indices 0-3, so Q1 (L=0) and Q3 (L=1) and Q0 (L=2) all sort into block 0 together, ordered by their own R — 3, then 6, then 9. Q2 (L=5) is the only query whose L falls in block 1, so it sorts last. The real processing order is therefore Q1, Q3, Q0, Q2, not the arrival order. Starting from an empty window (curL=0, curR=-1): answering Q1=[0,3] only ever expands right, adding indices 0-3 one at a time (values 1, 2, 1, 3 → distinct grows 1, 2, 2, 3). Moving to Q3=[1,6] expands right again (indices 4-6) and, only once, shrinks left by removing index 0 — a single step, because the next query's L is only one more than the current one. Moving to Q0=[2,9] repeats the pattern: expand right to 9, shrink left by removing index 1. Only the jump to Q2=[5,11], the one query in a different block, costs a real jump: left shrinks from 2 to 5 (three removals) while right still only expands by two. Every one of these moves is a single call to add or remove touching exactly one array index — the window is never rebuilt from scratch. Total pointer moves for this run: 17, confirmed by counting every add/remove call in the code that ships on this page. Answering the same four queries in their original, unsorted arrival order instead — which still gives the identical four answers, since the window ends up covering the same ranges either way — costs 42 moves on this same array: correct either way, but sorting first is 2.5× cheaper even on an array this small, and the gap widens sharply as n and m grow (see Pitfalls below).

Reference implementation

One frequency map, four pointer-adjustment loops, and a sort — the whole algorithm, specialized to distinct-count:

function mosAlgorithmDistinctCount(arr, queries) {
  const n = arr.length;
  const blockSize = Math.max(1, Math.round(Math.sqrt(n)));

  const order = queries.map((_, i) => i);
  order.sort((a, b) => {
    const blockA = Math.floor(queries[a][0] / blockSize);
    const blockB = Math.floor(queries[b][0] / blockSize);
    if (blockA !== blockB) return blockA - blockB;
    return queries[a][1] - queries[b][1];        // same block → break ties by R
  });

  const freq = new Map();
  let distinct = 0, curL = 0, curR = -1;

  function add(i) {
    const v = arr[i];
    const f = (freq.get(v) || 0) + 1;
    freq.set(v, f);
    if (f === 1) distinct++;                      // 0 → 1: this value just entered the window
  }
  function remove(i) {
    const v = arr[i];
    const f = freq.get(v) - 1;
    freq.set(v, f);
    if (f === 0) distinct--;                       // 1 → 0: this value just left the window
  }

  const answers = new Array(queries.length);
  for (const qi of order) {
    const [l, r] = queries[qi];
    while (curR < r) add(++curR);
    while (curL > l) add(--curL);
    while (curR > r) remove(curR--);
    while (curL < l) remove(curL++);
    answers[qi] = distinct;          // filled out of order, indexed by the query's original slot
  }
  return answers;
}

Verified against a naive O(n)-per-query distinct count (build a Set over arr[l..r] directly) across 2,000 randomized trials — random array lengths 1-40, random block sizes, random query ranges, zero mismatches — plus the specific default-demo numbers above traced by hand first.

Pitfalls

The sort isn't a style choice — it's the entire asymptotic argument, and skipping it costs an order of magnitude in practice, not just in theory. This page's own shipped demo measures 17 pointer moves sorted versus 42 unsorted on the tiny 12-element default array — real counts from the real code, toggle it above to reproduce them. At real scale the gap is far larger: a from-scratch script generating random queries over a 1,000-element array measured 39,469 total pointer moves with the block sort against 526,585 processing the same queries in their original order — 13.3× more work for an identical set of answers. At 2,000 elements and 2,000 queries the gap was 18.9× (113,688 versus 2,149,502 moves). The reason is structural, not incidental: sorting by block of L guarantees R only moves forward within each of the √n blocks (bounded total movement O(n) per block, O(n·√n) across all of them), and guarantees L only ever moves within one block's own √n-wide span per query (O(m·√n) total). Drop the sort and both guarantees disappear — R can be forced to sweep the entire array between adjacent queries with no bound at all, which is exactly what the measured 13-19× gap above is showing happening in practice.

The whole batch of queries has to be known before you start, and the array can't change while you're answering them. Every structure this category's own guide compares — segment tree, Fenwick tree, sparse table, all of them — answers whichever query arrives next, right now, with no visibility into what's coming later. Mo's Algorithm can't do that: reordering the queries is the entire mechanism, so it's unusable the moment a query needs an answer before the rest of the batch is even known, and a genuine "Mo's Algorithm with updates" variant exists for a changing array but adds a third sort dimension (time) and is materially more complex — not covered here. Reach for this only in an offline setting: a fixed report over a fixed dataset, not a live query stream.

Complexity

Time: O((n + m)·√n) for the entire batch of m queries together, not per query — sorting the queries is O(m log m), and the pointer-movement argument above bounds total add/remove calls at O(n·√n) + O(m·√n) = O((n + m)·√n). A single query's own share of that cost is amortized, not a fixed bound the way a segment tree's O(log n) applies to any one query in isolation. Space: O(n) for the frequency table (or O(V) for the value range, if values are small integers and a plain array is used instead of a map) plus O(m) to hold the queries and their sorted order.

A common further refinement — sort R ascending within even-numbered blocks and descending within odd-numbered ones, so the window's right pointer never has to snap back to a small value at a block boundary — trims the constant factor further without changing the asymptotic bound above; not implemented here, to keep this page's demo focused on the core block-sort mechanism rather than the tuning on top of it.

This site's guide, Choosing a Range Query Structure, sets this entry aside from the other six the same way it already sets Binary Heap aside — same category, genuinely different question: batch, offline, no update support, versus one online query at a time against a structure built to also handle changes.