Disjoint & Standard Sparse Tables: O(1) Idempotent Range Minimum Query (RMQ)

1. The Algebra of Range Queries: Semigroups, Monoids, Groups, and Idempotence

Before selecting a range query structure, classify the binary operator $\oplus: S \times S \to S$:

• Group (Invertible Associative Operation) — e.g., $+, \oplus(\text{XOR}), \times \pmod p$. Because every element has an inverse $a^{-1}$, any static range query $A[L \dots R]$ reduces to a 1D prefix array $P[i] = P[i-1] \oplus A[i]$ via $P[R] \oplus P[L-1]^{-1}$ in $O(N)$ build and $O(1)$ query time.
• Idempotent Semigroup (Band) — e.g., $\min, \max, \gcd, \text{lcm}, \&, |$. These operations have no inverse (knowing $\min(A[0..R]) = 2$ and $\min(A[0..L-1]) = 2$ tells you nothing about $\min(A[L..R])$), so prefix arrays fail. However, they satisfy idempotence: $x \oplus x = x$. Consequently, if two sub-intervals $I_1, I_2$ satisfy $I_1 \cup I_2 = [L, R]$, then $\text{ans}(I_1) \oplus \text{ans}(I_2) = \text{ans}([L, R])$ even when $I_1 \cap I_2 \neq \emptyset$.
• General Semigroup / Monoid (Non-Invertible, Non-Idempotent) — e.g., $2 \times 2$ matrix multiplication, polynomial hashing, maximum subarray sum tuple, string concatenation. Neither prefix inversion nor overlapping intervals work; we must partition $[L, R]$ into strictly disjoint intervals.

2. Standard Sparse Table Construction & Disjoint Sparse Table (DST)

The Standard Sparse Table builds a 2D table $\text{st}[k][i]$ of size $(\lfloor \log_2 N \rfloor + 1) \times N$, where $\text{st}[k][i]$ stores the range aggregate over $[i, i + 2^k - 1]$. Level $0$ is just $\text{st}[0][i] = A[i]$, and each subsequent level is built by combining two adjacent intervals of length $2^{k-1}$:

$$\text{st}[k][i] = \text{st}[k-1][i] \oplus \text{st}[k-1][i + 2^{k-1}]$$

In contrast, a Disjoint Sparse Table (DST) pads $N$ to a power of two $2^H$ and considers blocks of size $2^{H - h}$ at depth $h \in [0, H-1]$. Around the midpoint $M$ of each block, DST computes suffixes moving left from $M-1$ down to the block start, and prefixes moving right from $M$ up to the block end. For any query $L < R$, let $b = \lfloor \log_2(L \oplus R) \rfloor$ be the most significant bit where $L$ and $R$ differ. At level $h = H - 1 - b$, indices $L$ and $R$ fall into the left and right halves of the same block separated by midpoint $M$, so $\text{dst}[h][L] \oplus \text{dst}[h][R]$ combines $[L, M-1]$ and $[M, R]$ with zero overlap in $O(1)$ time!

3. Production Implementation: Standard RMQ & Disjoint Sparse Table

/**
 * 1. Standard Sparse Table for O(1) Idempotent Range Minimum Query (RMQ)
 * Build: O(N log N) time & space | Query: O(1) time (2 table lookups + 1 clz32)
 */
class SparseTableRMQ {
  constructor(arr) {
    this.n = arr.length;
    this.maxK = 31 - Math.clz32(this.n);
    // Flat Float64Array / Int32Array per level for L1/L2 cache locality
    this.st = Array.from({ length: this.maxK + 1 }, () => new Int32Array(this.n));
    for (let i = 0; i < this.n; i++) this.st[0][i] = arr[i];

    for (let k = 1; k <= this.maxK; k++) {
      const half = 1 << (k - 1);
      const limit = this.n - (1 << k);
      const prev = this.st[k - 1];
      const curr = this.st[k];
      for (let i = 0; i <= limit; i++) {
        const a = prev[i], b = prev[i + half];
        curr[i] = a < b ? a : b;
      }
    }
  }

  query(l, r) {
    const k = 31 - Math.clz32(r - l + 1);
    const row = this.st[k];
    const a = row[l], b = row[r - (1 << k) + 1];
    return a < b ? a : b;
  }
}

/**
 * 2. Disjoint Sparse Table (DST) for O(1) Non-Idempotent Semigroup Queries
 * Supports any associative combine(a, b) (e.g., modular product, matrix mult)
 */
class DisjointSparseTable {
  constructor(arr, combine) {
    this.combine = combine;
    this.levels = Math.max(1, 32 - Math.clz32(arr.length - 1));
    this.size = 1 << this.levels;
    this.table = Array.from({ length: this.levels }, () => new Array(this.size));

    for (let h = 0; h < this.levels; h++) {
      const blockLen = 1 << (this.levels - h);
      const half = blockLen >> 1;
      for (let start = 0; start < arr.length; start += blockLen) {
        const mid = Math.min(start + half, arr.length);
        const end = Math.min(start + blockLen, arr.length);
        // Suffixes extending left from mid - 1 down to start
        if (mid - 1 < arr.length) {
          this.table[h][mid - 1] = arr[mid - 1];
          for (let i = mid - 2; i >= start; i--) {
            this.table[h][i] = combine(arr[i], this.table[h][i + 1]);
          }
        }
        // Prefixes extending right from mid up to end - 1
        if (mid < arr.length) {
          this.table[h][mid] = arr[mid];
          for (let i = mid + 1; i < end; i++) {
            this.table[h][i] = combine(this.table[h][i - 1], arr[i]);
          }
        }
      }
    }
  }

  query(l, r) {
    if (l === r) return this.table[this.levels - 1][l];
    const msbDiff = 31 - Math.clz32(l ^ r);
    const h = this.levels - 1 - msbDiff;
    return this.combine(this.table[h][l], this.table[h][r]);
  }
}

4. Complexity Matrix