↩ back to Array-Backed Trees

±1 RMQ (Restricted Range Minimum Query)

Sparse Table answers a range-minimum query in O(1), but only after an O(n log n) build. Cartesian Tree's own Pitfalls section names the piece that gets a specific kind of array down to O(n) build and O(1) query: once every consecutive pair of values is known to differ by exactly ±1 — exactly what an Euler tour of a tree's depths produces, the reduction that page builds — the general range-minimum problem collapses into a much easier restricted one. This page is that structure: chop the array into small blocks, answer within-block queries with one precomputed lookup table shared by every block that happens to have the same relative up/down shape, and answer across-block queries with a sparse table — Sparse Table's own class, unmodified, just run over the blocks' minimums instead of the raw array.

Try it

The 14 values below step by exactly ±1 each time, the shape this structure requires. They're chopped into blocks of 3 (the tick marks), except the last, which is whatever is left over — 2 values here. Pick a query range and press Query, then step through to see exactly which blocks it touches and how each one gets resolved.

Why it works

Within one block, only the shape matters, not the actual values. A block of length b that steps by ±1 each time is fully described by b − 1 up/down bits — its actual starting value never affects which offset holds the minimum, only the sequence of ups and downs does. With block size 3 there are only 2² = 4 possible shapes, so the argmin of every one of a block's 6 possible sub-ranges can be precomputed once per shape and reused by every block that shares it — blocks 0 and 2 in the demo above both step up-up and share one table:

Each cell is an offset within the block (0, 1, or 2), not a value — block 1's real values are [1, 0, −1], shape DD, so a query for offsets [0,2] reads the DD row's [0,2] cell (offset 2) and reports global index 3 + 2 = 5, value −1. Only 4 shapes exist here because the demo's block size is 3; in general a block of size b has 2^(b−1) shapes, each needing O(b²) table entries — see Complexity below for why b has to grow slowly with n for this to stay cheap.

Across blocks, the answer is at most three pieces combined with min. A query spanning blocks bl through br is: whatever's left of block bl after its own start offset (a same-shape-table lookup, or a direct 1–2 element scan if bl is the short final block), whatever's left of block br before its own end offset (same choice), and — only if at least one whole block sits strictly between them — the minimum of those fully-covered blocks' own minimums. That last piece is exactly a range-minimum query over the array of per-block minimums, and the array of per-block minimums never changes once built, so it's answered by Sparse Table itself, unmodified: 5 blocks means 5 entries, ⌊log₂5⌋+1 = 3 rows, built and queried by the identical doubling logic that page already verified.

Reference implementation

Preprocessing builds the per-block minimums, tags each full-length block with its shape, fills one lookup table per distinct shape, then builds a sparse table over the block minimums:

function buildRestrictedRMQ(arr, blockSize) {
  const n = arr.length;
  const numBlocks = Math.ceil(n / blockSize);
  const blockMin = [], blockMinIdx = [], blockShape = [], blockLen = [];

  for (let b = 0; b < numBlocks; b++) {
    const start = b * blockSize, end = Math.min(start + blockSize, n);
    let mi = start, mv = arr[start];
    for (let i = start + 1; i < end; i++) if (arr[i] < mv) { mv = arr[i]; mi = i; }
    blockMin.push(mv); blockMinIdx.push(mi); blockLen.push(end - start);
    if (end - start === blockSize) {
      let shape = 0;
      for (let i = start + 1; i < end; i++) shape = (shape << 1) | (arr[i] > arr[i - 1] ? 1 : 0);
      blockShape.push(shape);
    } else {
      blockShape.push(-1);                 // final short block — resolved by direct scan instead
    }
  }

  const numShapes = 1 << (blockSize - 1);
  const PRECOMP = [];                      // PRECOMP[shape][i][j] = argmin offset within that shape
  for (let shape = 0; shape < numShapes; shape++) {
    const vals = [0];
    for (let k = 1; k < blockSize; k++) {
      vals.push(vals[k - 1] + (((shape >> (blockSize - 1 - k)) & 1) ? 1 : -1));
    }
    const table = [];
    for (let i = 0; i < blockSize; i++) {
      table.push(new Array(blockSize));
      let mi = i, mv = vals[i];
      table[i][i] = i;
      for (let j = i + 1; j < blockSize; j++) {
        if (vals[j] < mv) { mv = vals[j]; mi = j; }
        table[i][j] = mi;
      }
    }
    PRECOMP.push(table);
  }

  // Sparse Table's own build logic (see that page), run over blockMin instead of arr,
  // carrying blockMinIdx alongside so a "which index won" answer survives the combine.
  const K = Math.floor(Math.log2(numBlocks)) + 1;
  const stVal = [blockMin.slice()], stIdx = [blockMinIdx.slice()];
  for (let k = 1; k < K; k++) {
    const half = 1 << (k - 1), len = 1 << k, rowV = [], rowI = [];
    for (let i = 0; i + len <= numBlocks; i++) {
      const a = stVal[k - 1][i], b = stVal[k - 1][i + half];
      if (a <= b) { rowV.push(a); rowI.push(stIdx[k - 1][i]); }
      else { rowV.push(b); rowI.push(stIdx[k - 1][i + half]); }
    }
    stVal.push(rowV); stIdx.push(rowI);
  }
  function blocksMinIdx(bl, br) {                // Sparse Table's own query, over blocks
    const len = br - bl + 1, k = Math.floor(Math.log2(len)), half = 1 << k;
    const bStart = br - half + 1;
    return stVal[k][bl] <= stVal[k][bStart] ? stIdx[k][bl] : stIdx[k][bStart];
  }

  function blockRangeMinIdx(b, i, j) {           // offsets i..j within block b
    if (blockShape[b] !== -1) return b * blockSize + PRECOMP[blockShape[b]][i][j];
    const start = b * blockSize;                 // short final block: fixed size, direct scan is O(1)
    let mi = start + i, mv = arr[start + i];
    for (let k = start + i + 1; k <= start + j; k++) if (arr[k] < mv) { mv = arr[k]; mi = k; }
    return mi;
  }

  return function query(l, r) {
    const bl = Math.floor(l / blockSize), br = Math.floor(r / blockSize);
    if (bl === br) return blockRangeMinIdx(bl, l - bl * blockSize, r - bl * blockSize);
    let bestIdx = blockRangeMinIdx(bl, l - bl * blockSize, blockLen[bl] - 1);
    const rightIdx = blockRangeMinIdx(br, 0, r - br * blockSize);
    if (arr[rightIdx] < arr[bestIdx]) bestIdx = rightIdx;
    if (bl + 1 <= br - 1) {
      const midIdx = blocksMinIdx(bl + 1, br - 1);
      if (arr[midIdx] < arr[bestIdx]) bestIdx = midIdx;
    }
    return bestIdx;
  };
}

const query = buildRestrictedRMQ([0,1,2,1,0,-1,0,1,2,3,2,1,0,-1], 3);
query(1, 10);                            // 5 — value -1, no tree walk, no loop over the range

Pitfalls

Reusing the whole block's minimum for a query that only covers part of it. The across-block case above genuinely does use a full block's minimum untouched — so it's tempting to handle a query that lands entirely inside one block the identical way, ignoring the query's own start/end offsets and just returning that block's overall minimum. Measured directly: generating 20,000 same-block partial-range queries at random and comparing against an independent naive scan, that shortcut is wrong 44.8% of the time (8,456 of 18,870 exercised trials, after skipping single-element blocks with no partial range to get wrong) — because a block's minimum only equals a sub-range's minimum when the sub-range happens to include the offset where that minimum actually sits, which a uniformly random sub-range does less than half the time. The same-block branch has to route through the shape-lookup table (or the short-block scan) keyed on the query's actual offsets, exactly like the left- and right-partial pieces of a cross-block query already do — there's no shortcut available just because the query stays inside one block.

Block size has to shrink relative to n, or the "one lookup table per shape" trick stops being cheap. The whole point of precomputing per-shape tables is that there are only 2^(b−1) shapes for block size b — few enough that 2^(b−1)·b² total entries stays small. That only holds if b grows like (log₂n)/2, the standard choice: at n = 1,000,000 that's block size 9, for 2⁸·9² = 20,736 total precomputed entries — smaller than n itself. Picking a size unrelated to n — even one as modest as 20, fixed regardless of how big the array gets — blows that budget to 2¹⁹·20² ≈ 2.1×10⁸ entries at every array size, including ones far smaller than that table itself. The query still returns the right answer either way (this is a complexity pitfall, not a correctness one), but the preprocessing that was supposed to be the cheap, sub-linear part of an O(n) structure ends up dominating everything, including arrays several orders of magnitude smaller than the table.

Complexity

Time: O(n) to build — n/b blocks each cost O(b) to summarize (linear in total), the shape tables cost O(2^(b−1)·b²) once for the whole structure regardless of n, and the sparse table over n/b block minimums costs O((n/b)·log(n/b)) — with b = ⌊(log₂n)/2⌋, both of the last two terms work out to O(n) or smaller. Query is O(1): two shape-table lookups (or two short direct scans at the array's very end) plus one sparse-table lookup, never a loop over the range's own length. Space: O(n) — one entry per block for minimums and shapes, O(n) for the block-level sparse table (it has only n/b entries per row now, not n), plus the shape tables' own o(n) budget from the pitfall above. That's a real improvement over plain Sparse Table's O(n log n) build and space — the price is that it only works on this one restricted input shape, not an arbitrary array.

This structure exists specifically to close out Cartesian Tree's own deferred forward reference: chain that page's O(n) tree build, an Euler tour reduced to exactly this ±1 shape, and this page's O(n)-build/O(1)-query structure, and the result is O(1)-query lowest common ancestor with O(n) preprocessing overall — the full classic result Treap's own page names but doesn't build.