Skip to content

SparseTable ​

SparseTable precomputes an immutable range-minimum table over a fixed-size array of 32-bit integers, answering minimum queries in O(1) time after O(n log n) preprocessing.

Construction ​

SyntaxDescription
SparseTable(data)Build an RMQ table over the values in data

The table is built from a non-generic array of i32 values. Positions are zero-indexed from 0 to len - 1. The length may be zero. Once constructed the table is immutable: use SegmentTree when you need point updates.

Methods ​

MethodSignatureReturnsDescription
query(from: usize, to: usize) => i32i32Return the minimum of the range [from, to)
len() => usizeusizeReturn the number of positions
isEmpty() => booleanbooleanWhether the table has no positions

Ranges use an exclusive upper bound: query(from, to) returns the minimum of the elements at positions from through to - 1, so query(0, len) is the minimum over all positions. query aborts with a runtime error when from >= to or to > len.

Complexity ​

OperationTime Complexity
queryO(1)
lenO(1)
isEmptyO(1)

Examples ​

Construction ​

tyrus
import { SparseTable } from "tyrus:algorithm";

const st = SparseTable([7, 2, 9, 1, 5, 8, 3]);

query ​

tyrus
const st = SparseTable([7, 2, 9, 1, 5, 8, 3]);

print(st.query(0, 7));  // minimum of all seven values
print(st.query(0, 3));  // min(7, 2, 9)
print(st.query(2, 5));  // min(9, 1, 5)
print(st.query(1, 2));  // 2

len and isEmpty ​

tyrus
const empty: i32[] = [];
const st = SparseTable(empty);

print(st.isEmpty());  // true
print(st.len());      // 0