Sparse tables and range tricks

Where the earlier tools stop

Prefix sums answer "what is the sum of this range?" in O(1) because a sum can be undone: sum(l..r) = P[r+1] − P[l]. Take the same array and ask for the minimum of a range and the trick collapses — there is no way to subtract a minimum. The previous chapter's segment tree does answer it, in O(log n) per query, and it also accepts updates. That generality is paid for on every query: a descent through the tree with a recursive call or two per level.

Now remove the updates. The array is read once, then queried a million times: the lowest price in a date range, the weakest link in a stretch of a pipeline, the common divisor of a run of numbers. When nothing ever changes, you are free to do work up front that a mutable structure could not afford. The question this chapter starts from is: how much work up front buys a single comparison per query?

Storing every pair is out: n = 10⁵ gives about 5 × 10⁹ answers. The sparse table is the middle road between "store nothing" and "store everything": store the answer only for ranges whose length is a power of two. There are about n log n of those, and, as the next two sections show, any range is covered by two of them.

One honest note on priorities. For most interview questions a segment tree is fast enough and you already know it, so the sparse table is not something you need in every round. It earns its place in two situations: the range query sits inside a loop or a binary search, so a log factor multiplies, and the problem tells you the array is fixed. The bigger payoff is the doubling idea underneath it, which comes back in this chapter as binary lifting and again, in disguise, in several other techniques.

The sparse table: keep only the power-of-two blocks

Let table[j][i] be the answer for the block of length 2^j that starts at index i, that is, for a[i .. i + 2j − 1]. Row 0 is the array itself, since a block of length 1 is one element. The other rows follow from one observation: a block of length 2^j is two blocks of length 2^j−1 placed side by side. So, writing op for min, max or gcd,

table[j][i] = op(table[j-1][i], table[j-1][i + 2^(j-1)])

The block has to fit inside the array, so row j starts at index 0 and ends at index n − 2j: it has n − 2j + 1 entries. Rows exist for every j with 2^j ≤ n, which is ⌊log₂ n⌋ + 1 rows. Here is the whole table, for minimum, on an array of eight numbers.

Read one cell to see the recurrence. table[2][1] = 1 is the minimum of a[1..4] = 2, 4, 7, 1. It was built from table[1][1] = 2 (the block a[1..2]) and table[1][3] = 1 (the block a[3..4]), and min(2, 1) = 1. A dash is a block that would run past the end of the array, so no such cell is stored.

Querying in O(1) with two overlapping blocks

Take a query for a[l..r] of length len = r − l + 1. Let k = ⌊log₂ len⌋, the largest k with 2^k ≤ len. Two blocks of length 2^k cover the range: one starts at l, the other ends at r and so starts at r − 2k + 1. There is no gap between them, because 2^k+1 > len means two blocks are at least as long as the whole range. They usually overlap, in the middle.

To find k without a loop or a lookup table, use the position of the highest set bit of the length. Math.clz32(len) counts the leading zero bits in a 32-bit integer, so 31 − Math.clz32(len) is exactly ⌊log₂ len⌋. Checked in Node 24, it matches Math.floor(Math.log2(len)) for every length up to 2²⁴, but the bit version is integer arithmetic from start to finish, so there is never a question of a float rounding the wrong way. If you prefer, a precomputed array lg[i] = lg[i >> 1] + 1 does the same job.

Dry run: five queries for the minimum on the array from the table

Every query is two table reads and one op, whatever the length. The last row shows the degenerate case: with len = 1 both blocks are the same single element, which is fine for the same reason the overlaps are fine. In (0, 2) the element a[1] is inside both blocks.

Why it works only for idempotent operations

The overlap is the entire trick, and it is also the entire restriction. Every element in the overlap is folded into the answer twice. That is only safe when folding something in twice gives the same result as folding it in once, an idempotent operation: op(x, x) = x. Minimum, maximum, gcd, bitwise AND and bitwise OR all have this property. The answer to "what is the min of this set?" does not depend on how many times a member appears, as long as every member appears at least once, and that is exactly what two covering blocks guarantee.

A sum is the opposite case. Run the same two-block query for the sum of a[1..6] on the array above:

This is the same split as in the previous chapter, seen from the other side. A Fenwick tree needs an operation that can be undone (sum, XOR); a sparse table needs one that can be repeated (min, max, gcd). They cover different operations, and which one you need follows from the question.

The table is not useless for the other operations; it just loses the O(1). Any associative operation can be answered from the same rows in O(log n) by cutting the range into blocks that do not overlap: take the biggest power of two that still fits, then the biggest that fits in what remains, and so on. That is the binary representation of the length. For the sum of a[1..6], length 6 = 4 + 2, take table[2][1] = 14 for a[1..4], then table[1][5] = 9 for a[5..6], and 14 + 9 = 23. The order is left to right, so it also works for operations where order matters.

The complete sparse table

The class below takes the combining function as an argument, so one piece of code serves min, max, gcd and the rest. The rows are plain arrays of numbers; each row is shorter than the one before it by exactly the amount the block length grew.

class SparseTable {
  constructor(nums, combine) {
    this.combine = combine;
    const n = nums.length;
    this.table = [nums.slice()]; // level 0: blocks of length 1
    for (let j = 1; (1 << j) <= n; j++) {
      const prev = this.table[j - 1];
      const half = 1 << (j - 1);
      const row = new Array(n - (1 << j) + 1);
      for (let i = 0; i < row.length; i++) {
        row[i] = combine(prev[i], prev[i + half]); // two halves of the block at i
      }
      this.table.push(row);
    }
  }

  query(l, r) { // inclusive, needs 0 <= l <= r < n
    const k = 31 - Math.clz32(r - l + 1); // floor(log2(length))
    const left = this.table[k][l];
    const right = this.table[k][r - (1 << k) + 1]; // block that ends exactly at r
    return this.combine(left, right);
  }
}

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

const mins = new SparseTable([5, 2, 4, 7, 1, 3, 6, 2], Math.min);
mins.query(1, 6); // 1
mins.query(0, 2); // 2

const gcds = new SparseTable([12, 18, 24, 9, 6], gcd);
gcds.query(0, 2); // 6, the gcd of 12, 18, 24
gcds.query(1, 3); // 3, the gcd of 18, 24, 9

Cost: O(n log n) to build, and the memory bill

There are ⌊log₂ n⌋ + 1 rows, and every row has at most n entries, each filled with one op call, so the build is O(n log n) time and O(n log n) memory. The query does one subtraction, one clz32, two reads and one op: O(1), assuming op itself is constant time (gcd on machine integers takes a number of steps that grows with the logarithm of the values, so a gcd table has that extra factor per query).

Memory is the price, and it is worth putting numbers on it, because it is what decides whether the sparse table is the right choice.

Compare the structures you already have, at n = 10⁵: a prefix-sum array or Fenwick tree stores n + 1 numbers, and the segment tree of the last chapter allocates 4n = 400,000. The sparse table is about four times the segment tree there, and the gap widens with n because it carries the extra log n factor. For large n in JavaScript, build each row as an Int32Array (or Float64Array if values do not fit 32 bits): a typed array stores each entry in a fixed 4 or 8 bytes.

What about updates? Change a[i] and every cell whose block contains i is stale. Row j has up to 2^j such cells, so a single change can invalidate O(n) cells across the rows, and a mutable array wants a different structure. If the changes arrive in a batch and queries come afterwards, rebuilding once in O(n log n) is a legitimate plan.

Returning the position, not the value

Often the question is "where is the minimum?", not "what is it?". The fix is to store indices in the table and make the combining step compare the values those indices point at. The ties are the part to be careful about: when two candidates have equal values, keep the left one and the answer is the leftmost minimum of the range.

function buildArgMin(nums) {
  const pickIndex = (a, b) => (nums[b] < nums[a] ? b : a); // on a tie keep a, the smaller index
  const indices = nums.map((_, i) => i);
  return new SparseTable(indices, pickIndex);
}

For nums = [5, 2, 4, 7, 1, 3, 6, 2] the table built this way answers query(0, 7) with 4 and query(5, 7) with 7, the position of the 2 at the end. On [3, 1, 1, 1, 3], query(2, 4) returns 2, not 3 or 4, and query(0, 4) returns 1. This is still the idempotent trick: pickIndex(x, x) returns x, so a candidate that sits in the overlap cannot change the result.

Descending the table: the first index below a threshold

A second query the same table answers, and one that sets up the next section. Given a start index and a threshold x, find the first index at or after the start whose value is below x. A block whose minimum is at least x contains nothing you want, so you can skip all of it. Try the block sizes from the largest down to 1, and skip whenever a whole block is safe to skip.

function firstBelow(st, from, x) { // st is a SparseTable built with Math.min
  const n = st.table[0].length;
  let pos = from;
  for (let j = st.table.length - 1; j >= 0; j--) {
    if (pos + (1 << j) <= n && st.table[j][pos] >= x) pos += 1 << j; // the whole block is >= x: skip it
  }
  return pos < n ? pos : -1;
}

Why does the greedy order work? Say the answer is d positions after from, which means the first d values are all at least x. Skipping a block of length 2^j is allowed exactly when it fits inside those d positions. Going from the largest size to the smallest, the code takes each power of two that is still needed, which builds d in binary, one bit per row. So the cost is one step per row: O(log n) per query, with no op calls at all. If no value is below x, the walk ends at n and the function returns −1.

On [5, 2, 4, 7, 1, 3, 6, 2]: firstBelow(st, 0, 3) gives 1, firstBelow(st, 2, 2) gives 4, firstBelow(st, 5, 3) gives 7, and firstBelow(st, 0, 1) gives −1, because no value is below 1.

The table as a subroutine: longest subarray within a limit

Range minimum and maximum rarely stand alone in an interview; they are the inner step of something else. Take the sliding-window problem "find the longest subarray in which the largest and smallest values differ by at most limit". Growing the window to the right and shrinking it from the left is the two-pointer pattern, and the only thing it needs at each step is max − min over the current window. With two sparse tables that is two O(1) reads.

function longestWithinLimit(nums, limit) {
  const lows = new SparseTable(nums, Math.min);
  const highs = new SparseTable(nums, Math.max);
  let best = 0;
  let left = 0;
  for (let right = 0; right < nums.length; right++) {
    while (highs.query(left, right) - lows.query(left, right) > limit) left++;
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Dry run: longestWithinLimit([10, 1, 2, 4, 7, 2], 5)

The answer is 4, the window [2, 4, 7, 2]. The cost is O(n log n) for the two tables and O(n) queries after that, so O(n log n) overall.

Be straight with the interviewer about the alternative. A pair of monotonic deques (see monotonic stack and queue) solves this exact problem in O(n) time and O(n) memory, and the practice list has that problem under ex-longest-subarray-abs-diff-limit. The sparse table version is shorter to get right, and it keeps working when the ranges you ask about do not slide in one direction, for example when you binary search for the longest valid length, or when the queries are arbitrary pairs handed to you in a list.

Binary lifting: the same doubling, over ancestors

A tree of n nodes is given as a parent array, and you are asked, many times, for the k-th ancestor of a node: the node you reach by going up k parents. Walking up one parent at a time costs O(k), which is O(n) per query on a tree that is a long chain, and with 10⁵ nodes and 10⁵ queries that is the 10¹⁰ wall from the last chapter again.

The sparse table suggests the cure. It never stored every block length; it stored lengths 1, 2, 4, 8, ... and built each from two of the previous size. Do the same with jumps. Let up[j][v] be the node you reach from v by going up 2^j parents, or −1 if the root is passed on the way. A jump of 2^j steps is two jumps of 2^j−1 steps chained together:

up[j][v] = up[j-1][ up[j-1][v] ]      // but -1 stays -1

To answer a query, write k in binary. Going up k steps is the same as going up 2^j steps for every bit j that is set in k, since the bits add up to k, and every jump follows the one path toward the root, so the order does not matter. That is at most log₂ n jumps per query.

class AncestorTable {
  constructor(parent) { // parent[root] = -1
    const n = parent.length;
    this.n = n;
    let levels = 1;
    while ((1 << levels) < n) levels++; // 2^levels >= n, deeper than any node
    this.up = [parent.slice()]; // up[j][v] = the 2^j-th ancestor of v, or -1
    for (let j = 1; j < levels; j++) {
      const prev = this.up[j - 1];
      const row = new Array(n);
      for (let v = 0; v < n; v++) {
        row[v] = prev[v] === -1 ? -1 : prev[prev[v]]; // two jumps of 2^(j-1)
      }
      this.up.push(row);
    }
  }

  kthAncestor(node, k) {
    if (k >= this.n) return -1; // no node is that deep
    for (let j = 0; j < this.up.length && node !== -1; j++) {
      if ((k >> j) & 1) node = this.up[j][node];
    }
    return node;
  }
}

const tree = new AncestorTable([-1, 0, 0, 1, 1, 2, 4, 6]);
tree.kthAncestor(7, 3); // 1
tree.kthAncestor(7, 4); // 0
tree.kthAncestor(7, 5); // -1, node 7 has only four ancestors

Dry run: the tree 0←1, 0←2, 1←3, 1←4, 2←5, 4←6, 6←7

Row 1 is row 0 applied twice: for v = 6, up[0][6] = 4 and up[0][4] = 1, so up[1][6] = 1. Node 7's ancestors, nearest first, are 6, 4, 1, 0.

The build is O(n log n) time and memory, one row per bit, and a query is O(log n). The number of rows follows from the depth: no node has more than n − 1 ancestors, so with 2^rows ≥ n every k below n has all its set bits inside the rows, and the guard k >= this.n returns −1 for the rest. One difference from the dynamic programs you may have written on trees: row j depends only on row j − 1, never on a traversal order, so the parent array may list nodes in any order.

The table is not limited to "which node". A second table beside up can carry a value along each jump, for example the largest edge weight on the way, merged with Math.max when two jumps chain. The best-known application is the lowest common ancestor of two nodes: lift the deeper one until both sit at the same depth, then lift both together. That needs depths from a traversal, and it belongs with strongly connected components, bridges and Euler paths in the advanced graphs chapter, which builds the same table and puts the LCA on top of it.

No tree needed: the same idea on a functional graph

Doubling does not depend on the structure being a tree. Suppose every node has exactly one outgoing edge, next[v], and the graph may contain cycles (a train that always goes from station i to next[i]). Where are you after k steps, with k as large as 10¹²? Simulating is hopeless; squaring the table is not: after the j-th squaring, jump[v] is the station 2^j steps ahead.

function kthStep(next, start, k) {
  let levels = 1;
  while (2 ** levels <= k) levels++;
  let jump = next.slice(); // jump = the 2^0 table
  let node = start;
  for (let j = 0; j < levels; j++) {
    if (Math.floor(k / 2 ** j) % 2 === 1) node = jump[node];
    jump = jump.map((v) => jump[v]); // square the table: 2^j steps becomes 2^(j+1)
  }
  return node;
}

const next = [1, 2, 0, 3]; // 0 -> 1 -> 2 -> 0 and so on; station 3 loops on itself
kthStep(next, 0, 1e12); // 1, because 10^12 % 3 === 1
kthStep(next, 3, 1e12); // 3

This keeps one table and squares it in place, so memory stays O(n) and time is O(n log k). It reads each bit of k with Math.floor(k / 2 ** j) % 2 instead of (k >> j) & 1, because the bit operators in JavaScript first convert to a 32-bit integer and would silently cut off a k like 10¹². Walking until a node repeats also works for this problem, and avoids the table, but it has to treat the tail before the cycle and the cycle itself separately; the doubling version needs no such case split.

Sqrt decomposition: blocks of about √n

The next idea is the simplest of the chapter and the most forgiving. Cut the array into blocks of size B, and for every block keep the aggregate you care about, such as its sum. A range query then has three parts: single elements at the left end, whole blocks in the middle, single elements at the right end.

Choosing the block size, and the code

How many reads does one query cost? At most B − 1 loose cells on the left, B − 1 on the right, and about n / B whole blocks, so roughly 2B + n / B. Making B larger shortens the block list and lengthens the loose ends, and the reverse. The sum is smallest when the two terms balance, near B = √(n / 2), and anything close to √n has the same growth: O(√n) per query, which is why Math.floor(Math.sqrt(n)) is the usual choice and why the idea is named after the square root.

class SqrtSum {
  constructor(nums) {
    this.a = nums.slice();
    this.size = Math.max(1, Math.floor(Math.sqrt(nums.length)));
    this.blocks = new Array(Math.ceil(nums.length / this.size)).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.blocks[Math.floor(i / this.size)] += nums[i];
    }
  }

  update(i, value) {
    this.blocks[Math.floor(i / this.size)] += value - this.a[i]; // fix the block by the difference
    this.a[i] = value;
  }

  query(l, r) { // inclusive
    const first = Math.floor(l / this.size);
    const last = Math.floor(r / this.size);
    let sum = 0;
    if (first === last) {
      for (let i = l; i <= r; i++) sum += this.a[i]; // inside one block: just loop
      return sum;
    }
    for (let i = l; i < (first + 1) * this.size; i++) sum += this.a[i]; // tail of the first block
    for (let b = first + 1; b < last; b++) sum += this.blocks[b]; // whole blocks
    for (let i = last * this.size; i <= r; i++) sum += this.a[i]; // head of the last block
    return sum;
  }
}

const blocks = new SqrtSum([5, 2, 8, 1, 9, 3, 7, 4, 6, 10]);
blocks.query(2, 7); // 32 = 8 + 13 + (7 + 4)
blocks.update(4, 0);
blocks.query(2, 7); // 23

Dry run: the array from the figure

An update for a sum is O(1): the block total changes by the difference between the new and old value, and nothing else is touched. A build is O(n), one pass.

When the aggregate is a minimum, an update cannot correct the block total by a difference, because the old value may have been the minimum and you do not know the runner-up. The fix is to recompute the block from its cells, which costs O(B) = O(√n):

class SqrtMin {
  constructor(nums) {
    this.a = nums.slice();
    this.size = Math.max(1, Math.floor(Math.sqrt(nums.length)));
    this.blocks = [];
    for (let b = 0; b * this.size < nums.length; b++) this.blocks.push(this._scan(b));
  }

  _scan(b) {
    const from = b * this.size;
    const to = Math.min(from + this.size, this.a.length);
    let low = Infinity;
    for (let i = from; i < to; i++) low = Math.min(low, this.a[i]);
    return low;
  }

  update(i, value) {
    this.a[i] = value;
    const b = Math.floor(i / this.size);
    this.blocks[b] = this._scan(b); // a minimum cannot be fixed by a difference: rescan the block
  }

  query(l, r) {
    const first = Math.floor(l / this.size);
    const last = Math.floor(r / this.size);
    let low = Infinity;
    if (first === last) {
      for (let i = l; i <= r; i++) low = Math.min(low, this.a[i]);
      return low;
    }
    for (let i = l; i < (first + 1) * this.size; i++) low = Math.min(low, this.a[i]);
    for (let b = first + 1; b < last; b++) low = Math.min(low, this.blocks[b]);
    for (let i = last * this.size; i <= r; i++) low = Math.min(low, this.a[i]);
    return low;
  }
}

On [5, 2, 8, 1, 9, 3, 7, 4, 6, 10] the block minimums are [2, 1, 4, 10]. After update(3, 20), block 1 holds 20, 9, 3, so its minimum rises from 1 to 3, and query(2, 7) changes from 1 to 3.

Why use √n blocks at all when a segment tree gives O(log n)? For n = 10⁵ the block size is 316, so a worst-case query reads about 950 cells, against a few dozen tree nodes. The reason to choose blocks is what a block is allowed to hold. A segment-tree node must merge with its sibling in O(1). A block can hold anything you can rebuild in O(B): a sorted copy of its cells, a table of how often each value occurs, a bitset. "Count the elements at least x in a range, with updates" is the typical example: keep each block sorted, binary search inside every whole block, rebuild one block on an update. Another extension is the range add with range sum: put a pending lazy amount on each block, add to whole blocks by bumping the tag and the block total (delta * length), and add cell by cell at the two loose ends. The exercise ex-sqrt-range-add-range-sum builds exactly that.

Offline queries: sort them first

Everything so far answered each query the moment it arrived. Often the problem hands you the whole list of queries up front, and then you are free to answer them in any order you like and put the answers back in the original positions. That freedom is a technique by itself: pick an order in which one sweeping structure can answer each query at the right moment.

Here is the standard example. Given an array and queries [l, r, x], count how many elements of nums[l..r] are at most x. Answering one query at a time needs a structure that can ask about any position range and any value limit at once, which is heavy. But sort the queries by x. As x grows, the set of elements that are <= x only grows, so each element is switched on exactly once. Keep a Fenwick tree over positions, with a 1 at every switched-on position: a query is then a count of ones in [l, r], the difference of two prefix sums.

function countAtMost(nums, queries) { // queries[q] = [l, r, x]: how many of nums[l..r] are <= x
  const n = nums.length;
  const byValue = nums.map((_, i) => i).sort((a, b) => nums[a] - nums[b]);
  const byLimit = queries.map((_, q) => q).sort((a, b) => queries[a][2] - queries[b][2]);

  const tree = new Array(n + 1).fill(0); // Fenwick over positions: 1 = "this element is active"
  const activate = (i) => {
    for (let k = i + 1; k <= n; k += k & -k) tree[k]++;
  };
  const activeBefore = (i) => {
    let sum = 0;
    for (let k = i; k > 0; k -= k & -k) sum += tree[k]; // active elements in positions 0..i-1
    return sum;
  };

  const answer = new Array(queries.length);
  let next = 0;
  for (const q of byLimit) {
    const [l, r, x] = queries[q];
    while (next < n && nums[byValue[next]] <= x) activate(byValue[next++]);
    answer[q] = activeBefore(r + 1) - activeBefore(l);
  }
  return answer;
}

Dry run: nums = [4, 1, 3, 1, 5, 2]

The queries are q0 = (1, 4, 2), q1 = (0, 5, 3), q2 = (2, 3, 1), q3 = (0, 2, 4). The positions in order of value are byValue = [1, 3, 5, 2, 0, 4], which are the values 1, 1, 2, 3, 4, 5.

The answers go back to their original slots by query number, so the output is [2, 4, 1, 3]. The cost is the two sorts, O(n log n + q log q), plus a Fenwick update per element and two prefix queries per query: O((n + q) log (n + q)) in total.

A second flavour of the same idea sorts the queries by their right end. The question is "how many distinct values are in nums[l..r]?". Sweep a right pointer across the array, and keep a 1 only at the latest occurrence so far of each value: when position p brings a value that was already seen, clear the old 1 and set a new one at p. At the moment the sweep has reached r, a value occurs in [l, r] exactly when its latest occurrence at or before r is at or after l, so the number of ones in [l, r] is the number of distinct values there.

function distinctInRanges(nums, queries) { // queries[q] = [l, r]
  const n = nums.length;
  const byRight = queries.map((_, q) => q).sort((a, b) => queries[a][1] - queries[b][1]);
  const tree = new Array(n + 1).fill(0);
  const add = (i, delta) => {
    for (let k = i + 1; k <= n; k += k & -k) tree[k] += delta;
  };
  const before = (i) => {
    let sum = 0;
    for (let k = i; k > 0; k -= k & -k) sum += tree[k];
    return sum;
  };

  const lastSeen = new Map();
  const answer = new Array(queries.length);
  let next = 0;
  for (const q of byRight) {
    const [l, r] = queries[q];
    while (next <= r) {
      const value = nums[next];
      if (lastSeen.has(value)) add(lastSeen.get(value), -1); // only the latest copy counts
      add(next, 1);
      lastSeen.set(value, next);
      next++;
    }
    answer[q] = before(r + 1) - before(l);
  }
  return answer;
}

countAtMost([4, 1, 3, 1, 5, 2], [[1, 4, 2], [0, 5, 3], [2, 3, 1], [0, 2, 4]]); // [2, 4, 1, 3]
distinctInRanges([3, 1, 3, 2, 1, 2, 3, 1], [[1, 4], [0, 2], [3, 5]]); // [3, 2, 2]

Dry run: nums = [3, 1, 3, 2, 1, 2, 3, 1], marked positions as the right end advances

Mo's algorithm: sorting queries so a window barely moves

This one is mention-level for interviews: it appears rarely, and you will seldom be asked to write it. It is worth knowing because it solves range queries that nothing else in this chapter can touch, and the idea is a small step from the offline section.

Suppose you can maintain the answer for a window nums[curL..curR] as elements are added or removed at either end, each in O(1), as with a table of counts per value. Then moving the window from one query to the next costs |curL − l| + |curR − r| element moves. If the queries are answered in the order they were given, that can be O(n) per query. Mo's observation: the queries are offline, so reorder them to make the total movement small.

Cut the array into blocks of size B = ⌊√n⌋. Sort the queries by the block that contains l, and inside one block by r ascending. Now count the movement. Inside a block, l stays within B positions of where it was, so the left pointer moves at most B per query, O(qB) in total. Inside a block the queries come in ascending order of r, so the right pointer sweeps rightward, at most n positions, before it moves back for the next block. There are n / B blocks, so it moves O(n · n / B) in total. With B = √n the two terms are O(q√n) and O(n√n): O((n + q)√n) moves.

function distinctWithMo(nums, queries) { // queries[q] = [l, r], inclusive
  const block = Math.max(1, Math.floor(Math.sqrt(nums.length)));
  const order = queries.map((_, q) => q).sort((a, b) => {
    const blockA = Math.floor(queries[a][0] / block);
    const blockB = Math.floor(queries[b][0] / block);
    if (blockA !== blockB) return blockA - blockB;
    return blockA % 2 === 0 ? queries[a][1] - queries[b][1] : queries[b][1] - queries[a][1];
  });

  const count = new Map();
  let distinct = 0;
  const add = (i) => {
    const c = (count.get(nums[i]) ?? 0) + 1;
    count.set(nums[i], c);
    if (c === 1) distinct++;
  };
  const remove = (i) => {
    const c = count.get(nums[i]) - 1;
    count.set(nums[i], c);
    if (c === 0) distinct--;
  };

  let curL = 0;
  let curR = -1; // the window nums[curL..curR] starts empty
  const answer = new Array(queries.length);
  for (const q of order) {
    const [l, r] = queries[q];
    while (curL > l) add(--curL); // grow first ...
    while (curR < r) add(++curR);
    while (curL < l) remove(curL++); // ... then shrink
    while (curR > r) remove(curR--);
    answer[q] = distinct;
  }
  return answer;
}

const nums = [3, 1, 3, 2, 1, 2, 3, 1];
distinctWithMo(nums, [[1, 4], [5, 7], [2, 6], [0, 2], [3, 5]]); // [3, 3, 3, 2, 2]

The comparator reverses the direction of r in every odd block. That is a constant-factor trick: the right pointer then sweeps back instead of teleporting back to the left, and the bound is unchanged. Remove the blockA % 2 test and the algorithm is still correct.

Dry run: nums = [3, 1, 3, 2, 1, 2, 3, 1], five queries, block size ⌊√8⌋ = 2

The queries in the order they were given: q0 = (1, 4), q1 = (5, 7), q2 = (2, 6), q3 = (0, 2), q4 = (3, 5). Their blocks of l are 0, 2, 1, 0, 1, so the sorted order is block 0 by r ascending (q3, q0), block 1 by r descending (q2, q4) and block 2 (q1). The window starts empty, at curL = 0, curR = −1.

The total is 15 element moves. Taking the same five queries in the order given would cost 29, and the gap grows quickly with n. The answers, put back in the original order, are [3, 3, 3, 2, 2].

Choosing among prefix sums, sparse table, Fenwick, segment tree and blocks

Two questions settle most of the choice. Does the array change? And what is the operation: can it be undone (sum, XOR), repeated (min, max, gcd), or neither of those but still associative (a pair of values, a matrix product)?

Recognizing it in an unseen problem

• The array is never modified and the questions are many ranges with the operation min, max or gcd (or AND, OR): sparse table. The word "static" or "immutable" in the statement is the cue.
• A range minimum or maximum appears inside a loop or a binary search (for each i, find the farthest j such that ...): an O(1) query keeps the whole solution at O(n log n) instead of O(n log² n).
• Updates arrive between queries: not a sparse table; a Fenwick tree for sums, a segment tree for min, max or gcd.
• "The k-th ancestor", "jump k steps", "after 10⁹ moves, where are you?", with every node having one successor: binary lifting, one jump per bit of k.
• The aggregate is awkward to merge but easy to recompute for a small block (count of values at least x with updates, most frequent value): sqrt decomposition.
• You can read every query before answering any, and the question is a count over a position range and a value condition: sort the queries by that value (or by right endpoint) and sweep with a Fenwick tree.
• "Number of distinct values", "sum of squared counts", or another window statistic over many ranges, without updates: Mo's algorithm, once you have ruled out the offline sweep.
• Distinguish from a sliding window of fixed shape: if the window only slides forward, the monotonic deque is O(n) and needs no table.