Skip to content

SparseTable ​

SparseTable precomputa una tabla inmutable de mínimo por intervalo sobre un arreglo de tamaño fijo de enteros de 32 bits, respondiendo consultas de mínimo en O(1) después de un preprocesamiento de O(n log n).

Construcción ​

SintaxisDescripción
SparseTable(data)Construye una tabla RMQ sobre los valores en data

La tabla se construye a partir de un arreglo no genérico de valores i32. Las posiciones se indexan desde cero, de 0 a len - 1. La longitud puede ser cero. Una vez construida, la tabla es inmutable: usa SegmentTree cuando necesites actualizaciones puntuales.

Métodos ​

MétodoFirmaRetornaDescripción
query(from: usize, to: usize) => i32i32Retorna el mínimo del intervalo [from, to)
len() => usizeusizeRetorna el número de posiciones
isEmpty() => booleanbooleanSi la tabla no tiene posiciones

Los intervalos usan límite superior exclusivo: query(from, to) retorna el mínimo de los elementos en las posiciones from hasta to - 1, así que query(0, len) es el mínimo sobre todas las posiciones. query aborta con error de runtime cuando from >= to o to > len.

Complejidad ​

OperaciónComplejidad Temporal
queryO(1)
lenO(1)
isEmptyO(1)

Ejemplos ​

Construcción ​

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 y isEmpty ​

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

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