↩ back to Array-Backed Trees

Mo's Algorithm with Updates

Mo's Algorithm answers a fixed batch of range queries over an array that never changes while the batch is being answered — that restriction is exactly what buys its O((n+m)√n) bound, and its own page names the natural next question it leaves open: what if the array does change, through point updates interleaved among the queries, as long as the whole batch (every query and every update, in order) is still known up front? This page is that variant. The trick is one more sort key: alongside block of L and block of R, each query also carries a time — how many updates had already landed before it was asked — and processing walks that dimension with the exact same one-step-at-a-time discipline as the window itself, applying or undoing one update's write at a time rather than rebuilding anything from scratch.

Try it

The array below has 12 values, indexed 0 through 11, split into blocks of size 5 (block width here is ⌈12^(2/3)⌉ = 5, not ⌈√12⌉ = 4 — see Pitfalls for why that matters). Six operations follow it in their original arrival order: four "how many distinct values in this range?" queries and two point updates, listed as Q0, U0, Q1, Q2, U1, Q3. Leave the checkbox on and press Load, then Step through — watch the window slide and the array's own values change as updates land, in an order that is neither the queries' arrival order nor a single pass through the array. Then untick the checkbox, reload, and step through the identical six operations processed in their plain arrival order instead: same four final answers, more total pointer-and-update moves to get there.

Why it works

The default array is [1, 2, 1, 3, 2, 4, 1, 3, 3, 2, 4, 1] (the same base array Mo's Algorithm uses). Arrival order is Q0=[2,9], U0: index 5 → 2, Q1=[0,3], Q2=[5,11], U1: index 9 → 1, Q3=[1,6] — so Q0 is asked at time 0 (no updates yet), Q1 and Q2 at time 1 (after U0), and Q3 at time 2 (after both). Block width 5 puts L=0 (Q1) and L=1 (Q3) and L=2 (Q0) all in block 0, with L=5 (Q2) alone in block 1. Within block 0, the tie breaks on block of R: Q1's R=3 is block 0 by itself; Q0's R=9 and Q3's R=6 are both block 1, so that tie breaks on time — Q0 (time 0) before Q3 (time 2). The real processing order is therefore Q1, Q0, Q3, Q2, not the arrival order Q0, Q1, Q2, Q3.

Starting from an empty window and time 0: Q1 expands right to [0,3], four adds, distinct 3 — no update needed yet, U0 hasn't happened at time 1... except Q1 is asked at time 1, so before answering it the time pointer has to step forward once, applying U0 (index 5, outside the current window, so only the array's own value changes, no frequency-table update at all). Moving to Q0 (time 0, window [2,9]): the window expands right past index 5, and because time must now step backward to 0, undoing U0 — and this time index 5 is inside the window, so undoing it means removing the value U0 wrote and re-adding the original one, same single-element discipline as any other window move. Moving to Q3 (time 2, window [1,6]) re-applies U0 (back inside the window again) and then U1 (index 9, currently outside the window, array-only). Moving finally to Q2 (time 1, window [5,11]) pulls index 9 into the window and has to undo U1 right there, inside the window this time. Every one of these — window adds/removes and update apply/undo alike — touches exactly one array index and updates the frequency table by at most one entry; nothing is ever rebuilt from scratch. Total moves for this run: 36, confirmed by counting every such step in the code that ships on this page. Answering the same six operations in plain arrival order instead — still correct, since arrival order is already the true chronological order, no time pointer ever needs to jump backward — costs 48 moves on this same array: correct either way, but the reordering is 25% cheaper even at this tiny size, and the gap widens sharply at scale (see Pitfalls below).

Reference implementation

One frequency map, six pointer/time-adjustment loops instead of plain Mo's four, and a three-key sort — specialized to distinct-count, matching the no-updates version's own reference implementation apart from the added time dimension:

function mosAlgorithmWithUpdates(arr, ops) {
  // ops: { type: 'query', l, r } or { type: 'update', pos, val }, in true arrival order
  const n = arr.length;
  const blockSize = Math.max(1, Math.round(Math.cbrt(n * n)));   // n^(2/3), not sqrt(n)

  const updates = [];   // { pos, oldVal, newVal }, one per update, in arrival order
  const queries = [];   // { l, r, time }, time = how many updates preceded this query
  const original = arr.slice();
  let time = 0;
  for (const op of ops) {
    if (op.type === 'update') {
      updates.push({ pos: op.pos, oldVal: original[op.pos], newVal: op.val });
      original[op.pos] = op.val;
      time++;
    } else {
      queries.push({ l: op.l, r: op.r, time });
    }
  }

  const order = queries.map((_, i) => i);
  order.sort((a, b) => {
    const qa = queries[a], qb = queries[b];
    const blA = Math.floor(qa.l / blockSize), blB = Math.floor(qb.l / blockSize);
    if (blA !== blB) return blA - blB;
    const brA = Math.floor(qa.r / blockSize), brB = Math.floor(qb.r / blockSize);
    if (brA !== brB) return brA - brB;
    return qa.time - qb.time;              // same (block L, block R) → break ties by time
  });

  const work = arr.slice();
  const freq = new Map();
  let distinct = 0, curL = 0, curR = -1, curT = 0;

  function add(i) {
    const f = (freq.get(work[i]) || 0) + 1;
    freq.set(work[i], f);
    if (f === 1) distinct++;
  }
  function remove(i) {
    const f = freq.get(work[i]) - 1;
    freq.set(work[i], f);
    if (f === 0) distinct--;
  }
  function applyForward() {
    const u = updates[curT];
    const inWindow = u.pos >= curL && u.pos <= curR;
    if (inWindow) remove(u.pos);
    work[u.pos] = u.newVal;                 // unconditional — see Pitfalls
    if (inWindow) add(u.pos);
    curT++;
  }
  function undoBackward() {
    curT--;
    const u = updates[curT];
    const inWindow = u.pos >= curL && u.pos <= curR;
    if (inWindow) remove(u.pos);
    work[u.pos] = u.oldVal;                 // unconditional — see Pitfalls
    if (inWindow) add(u.pos);
  }

  const answers = new Array(queries.length);
  for (const qi of order) {
    const q = queries[qi];
    while (curR < q.r) add(++curR);
    while (curL > q.l) add(--curL);
    while (curR > q.r) remove(curR--);
    while (curL < q.l) remove(curL++);
    while (curT < q.time) applyForward();
    while (curT > q.time) undoBackward();
    answers[qi] = distinct;
  }
  return answers;
}

Verified against a from-scratch reference that just applies each operation directly against a mutable array in true arrival order and computes a query's distinct count from scratch with a Set — 10,000 randomized trials (array lengths 1-25, 1-18 operations per trial, a random mix of queries and point updates), zero mismatches — plus the six-operation trace above confirmed by hand first.

Pitfalls

The block width has to be n^(2/3), not plain Mo's Algorithm's √n — reusing the no-updates formula still gives correct answers, just measurably more work. With three quantities to bound instead of two (L movement, R movement, and now time movement), a wider block trades a little more per-query L/time movement for a lot less total R movement across groups, and n^(2/3) is the width that balances those three costs — √n balances only the first two. A from-scratch script generating random batches of queries and point updates measured 100,351 average total moves with block width n^(2/3) against 160,740 with block width √n on a 1,000-element array with 1,000 operations (200 trials) — 1.60× more work for identical answers. At 2,000 elements and 2,000 operations the gap was 1.83× (327,799 versus 600,022 moves, 100 trials). Smaller than plain Mo's Algorithm's own sort-versus-no-sort gap, because both block widths here are still real, deliberate choices — this is a tuning mistake, not the correctness-breaking absence of a sort entirely.

An update's write to the array has to happen unconditionally — only the frequency-table side of it is allowed to depend on whether the position is currently inside the window. A natural-looking shortcut skips writing work[u.pos] at all when the position sits outside [curL, curR], reasoning that nothing is watching that index right now anyway. It isn't watching yet — but the window moves, and a later step that slides the position into view reads work[u.pos] expecting it to already reflect every update up to the current time, not just the ones that happened to land while that position was in view. Stress-tested against the same from-scratch reference across 20,000 randomized trials: 22.7% wrong. Smallest hand-checkable case: array [1, 2, 3, 4, 5, 6], one update (index 4 → 6), then query [0, 2], then query [3, 5]. The first query never touches index 4, so the skip never gets corrected before the second query slides it into view still holding its stale value 5 instead of the update's 6 — correct answers are [3, 2] (the second query's window is {4, 6, 6}, two distinct values), the shortcut answers [3, 3] (it sees {4, 5, 6} instead, three).

Complexity

Time: O((n + q)·n^(2/3)) for the entire batch, where q is the combined count of queries and updates — sorting is O(q log q), and the same argument that bounds plain Mo's Algorithm's pointer movement at O((n+m)√n) now applies to three quantities balanced against the same n^(2/3) block width instead of two balanced against √n: each query's own L, R, and time movement is bounded by a block's width, and the total movement across all queries stays polynomial in n and q rather than degrading to the O(q·n) a completely unsorted batch could cost. Space: O(n) for the frequency table plus O(q) to hold the operations, their sorted order, and every update's before/after value pair for undoing.

This is strictly a point-update extension — an update that has to touch a whole range at once (the same distinction this category's own guide draws between Segment Tree and Segment Tree with Lazy Propagation) isn't covered by this technique at all; a single "add 10 to every element in this range" update would have to be decomposed into per-element updates first, defeating the point. Reach for this over a persistent or lazy tree structure specifically when the query itself has no efficient merge operation — the same condition plain Mo's Algorithm's own page names for the no-updates case — and the whole batch, updates included, is genuinely known in advance.