Skip to content

SparseTable ​

SparseTable pré-computa uma tabela imutável de mínimo por intervalo sobre um array de tamanho fixo de inteiros de 32 bits, respondendo consultas de mínimo em O(1) após um pré-processamento de O(n log n).

Construção ​

SintaxeDescrição
SparseTable(data)Constrói uma tabela RMQ sobre os valores em data

A tabela é construída a partir de um array não genérico de valores i32. As posições são indexadas a partir de zero, de 0 a len - 1. O comprimento pode ser zero. Uma vez construída, a tabela é imutável: use SegmentTree quando precisar de atualizações pontuais.

Métodos ​

MétodoAssinaturaRetornaDescrição
query(from: usize, to: usize) => i32i32Retorna o mínimo do intervalo [from, to)
len() => usizeusizeRetorna o número de posições
isEmpty() => booleanbooleanSe a tabela não tem posições

Os intervalos usam limite superior exclusivo: query(from, to) retorna o mínimo dos elementos nas posições from até to - 1, então query(0, len) é o mínimo sobre todas as posições. query aborta com erro de runtime quando from >= to ou to > len.

Complexidade ​

OperaçãoComplexidade Temporal
queryO(1)
lenO(1)
isEmptyO(1)

Exemplos ​

Construção ​

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

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

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