Crate sparse_table 

Sparse Table for idempotent range queries.

A Sparse Table answers range queries on a static array in O(1) query time after O(n log n) preprocessing, as long as the query operation is idempotent and associative. The classic examples are min, max, and gcd. (Sum works too; xor works too.)

The trick: precompute st[k][i] = op(a[i], a[i+1], ..., a[i+2^k-1]) and overlap two intervals of length 2^k to cover any range [l, r].

Example

use sparse_table::SparseTable;

let a = vec![1, 3, 2, 5, 4];
let st = SparseTable::new(&a, |x, y| if x < y { x } else { y });
assert_eq!(st.query(1, 4), Some(2)); // min over [1, 4) = min(3, 2, 5) = 2
assert_eq!(st.query(0, 5), Some(1)); // min over whole array

Structs

SparseTable

Sparse Table for idempotent, associative operations on a static array.

Functions

gcd_sparse_table

Convenience constructor for gcd queries.

max_sparse_table

Convenience constructor for max queries.

min_sparse_table

Convenience constructor for min queries.