√N Block Decomposition & Mo's Offline Query Ordering (O((N+Q)√N))

1. Online $\sqrt{N}$ Block Decomposition vs Offline Mo's Algorithm

There are two primary ways to apply square-root decomposition to array range queries:

• Online $\sqrt{N}$ Block Decomposition: Partition $A[0..N-1]$ into $\lceil N / B \rceil$ blocks of size $B \approx \sqrt{N}$. Each block maintains a summary (or sorted copy / frequency bucket). A range query $[L, R]$ inspects at most $\lceil N / B \rceil$ full blocks in the interior plus at most $2B$ individual elements in the two partial boundary blocks ($\lfloor L/B \rfloor$ and $\lfloor R/B \rfloor$), taking $O(B + N/B) = O(\sqrt{N})$ time.
• Offline Mo's Algorithm: Reorders $Q$ static queries $[L_i, R_i]$ so a single sliding window $[\text{curL}, \text{curR}]$ visits all queries with minimal total Manhattan movement $\sum (|L_i - L_{i-1}| + |R_i - R_{i-1}|)$.

2. Critical Implementation Rule: Expand Window Before Contracting!

When transitioning the active window $[\text{curL}, \text{curR}]$ to target $[L, R]$, the order of the four while loops is critical! If you execute remove(curL++) or remove(curR--) before expanding add(--curL) and add(++curR), and the new query $[L, R]$ is disjoint from $[\text{curL}, \text{curR}]$, the intermediate window transiently becomes inverted ($\text{curL} > \text{curR} + 1$) with negative element counts! Always run the two expansion loops (--curL, ++curR) first, and the two contraction loops (curL++, curR--) second.

3. Production Implementation: Online $\sqrt{N}$ Decomposition & Offline Mo's Algorithm

/**
 * 1. Online Sqrt Block Decomposition for Range Sum + Point Update
 * Block size B = ceil(sqrt(N)) | Point Update: O(1) | Range Query: O(sqrt(N))
 */
class SqrtBlockDecomposition {
  constructor(arr) {
    this.n = arr.length;
    this.B = Math.max(1, Math.ceil(Math.sqrt(this.n)));
    this.arr = Float64Array.from(arr);
    this.blocks = new Float64Array(Math.ceil(this.n / this.B));
    for (let i = 0; i < this.n; i++) {
      this.blocks[Math.floor(i / this.B)] += this.arr[i];
    }
  }

  update(idx, newVal) {
    const b = Math.floor(idx / this.B);
    this.blocks[b] += newVal - this.arr[idx];
    this.arr[idx] = newVal;
  }

  query(l, r) {
    let sum = 0;
    const bL = Math.floor(l / this.B);
    const bR = Math.floor(r / this.B);
    if (bL === bR) {
      for (let i = l; i <= r; i++) sum += this.arr[i];
      return sum;
    }
    for (let i = l, end = (bL + 1) * this.B; i < end; i++) sum += this.arr[i];
    for (let b = bL + 1; b < bR; b++) sum += this.blocks[b];
    for (let i = bR * this.B; i <= r; i++) sum += this.arr[i];
    return sum;
  }
}

/**
 * 2. Offline Mo's Algorithm with Boustrophedon (Snake) Ordering
 * Example: Count distinct values in each query [l, r] in O((N + Q) sqrt(N))
 */
function mosDistinctQueries(arr, queries) {
  const n = arr.length;
  const q = queries.length;
  const B = Math.max(1, Math.floor(n / Math.sqrt(Math.max(1, q))));

  // Coordinate compress arr into [0 .. M-1] so freq[] fits in a fast Int32Array
  const unique = Array.from(new Set(arr)).sort((a, b) => a - b);
  const rankMap = new Map(unique.map((v, idx) => [v, idx]));
  const a = Int32Array.from(arr, (v) => rankMap.get(v));

  const indexedQueries = queries.map(([l, r], idx) => ({
    l,
    r,
    idx,
    block: Math.floor(l / B)
  }));

  // Snake order sort: primary by L-block, secondary by R (asc on even block, desc on odd block)
  indexedQueries.sort((q1, q2) => {
    if (q1.block !== q2.block) return q1.block - q2.block;
    return (q1.block & 1) ? (q2.r - q1.r) : (q1.r - q2.r);
  });

  const freq = new Int32Array(unique.length);
  const answers = new Int32Array(q);
  let distinct = 0;
  let curL = 0, curR = -1;

  for (let i = 0; i < q; i++) {
    const { l, r, idx } = indexedQueries[i];
    // ALWAYS expand (--curL, ++curR) BEFORE contracting (curL++, curR--)!
    while (curL > l) {
      const val = a[--curL];
      if (++freq[val] === 1) distinct++;
    }
    while (curR < r) {
      const val = a[++curR];
      if (++freq[val] === 1) distinct++;
    }
    while (curL < l) {
      const val = a[curL++];
      if (--freq[val] === 0) distinct--;
    }
    while (curR > r) {
      const val = a[curR--];
      if (--freq[val] === 0) distinct--;
    }
    answers[idx] = distinct;
  }
  return answers;
}

4. Complexity Matrix