TypeScript implementation of Range Minimum Query (RMQ) using Sparse Table

rmq.ts

function getP(x: number): number {
  return Math.floor(Math.log2(x))
}

export interface ResultPair<T> {
  value: T
  index: number
}

export function rmq<T>(
  itr: Iterable<T>,
  op: (a: T, b: T) => { value: T; isFromA?: boolean },
  isOverlapping: boolean,
): (index0: number, index1: number) => ResultPair<T> {
  const table = [] as ResultPair<T>[][]

  let N = 0
  table[0] = []
  for (const x of itr) {
    table[0][N] = { value: x, index: N }
    N += 1
  }

  const P = getP(N)
  for (let p = 1; p <= P; ++p) {
    table[p] = []

    const L = 2 ** (p - 1)
    for (let n = 0; n + 2 * L - 1 < N; ++n) {
      const { value, isFromA } = op(
        table[p - 1][n].value,
        table[p - 1][n + L].value,
      )
      table[p][n] = {
        value,
        index: isFromA ? table[p - 1][n].index : table[p - 1][n + L].index,
      }
    }
  }

  return function query(index0: number, index1: number): ResultPair<T> {
    const P = getP(index1 - index0 + 1)
    const L = 2 ** P

    if (isOverlapping) {
      const { value, isFromA } = op(
        table[P][index0].value,
        table[P][index1 - L + 1].value,
      )
      return {
        value,
        index: isFromA
          ? table[P][index0].index
          : table[P][index1 - L + 1].index,
      }
    }
    if (index1 - index0 + 1 > L) {
      const { value: rvalue, index: rindex } = query(index0 + L, index1)
      const { value, isFromA } = op(table[P][index0].value, rvalue)
      return {
        value,
        index: isFromA ? table[P][index0].index : rindex,
      }
    }
    return table[P][index0]
  }
}

RMQ (Range Minimum Query) is a problem of processing some values along the intervals. Sparse table is a genius dynamic programming approach for solving RMQ. There is a great explanation video on WilliamFiset's Youtube channel, so if you're curious about how it works, please check that out.

Sparse Table holds O(N lg N) spaces, and needs O(N lg N) operations for construction. Note that this implementation returns the value with the index. If you don't need the index, just modify slightly. Also index can be meaningless with respect to some kind of operations. For example, since summation makes completely new value, you don't have to set isFromA.

Example

const values = [1, 5, 2, 10, 3, 7]
const query = rmq(values, (a, b) => ({ value: Math.min(a, b), isFromA: a < b }), true)

console.log(query(0, 3)) // 1
console.log(query(2, 5)) // 2

Operation's Property

To use this algorithm, operation must satisfies the associativity property. And if the operation also satisfies overlap friendly property, then the performance gets better.

Associativity

A binary operation f is associative, iff f(f(a, b), c) = f(a, f(b, c)) for all a, b, c in the domain of f.

If f is associative, then RMQ can query with in O(lg N) time complexity. Example of this kind of operations are following:

• a + b
• a * b
• gcd(a, b)
• min(a, b)
• lca(a, b) // least common ancestor

Overlap Friendly

A binary operation f is overlap friendly, iff f(f(a, b), f(b, c)) = f(f(a, b), c) for all a, b, c in the domain of f.

If f is overlap friendly, then RMQ can query with in O(1) times complexity. Example of this kind of operations are following:

• gcd(a, b)
• min(a, b)
• lca(a, b)