Struct SparseTable 

pub struct SparseTable<T, F: Fn(T, T) -> T> { /* private fields */ }

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

Implementations

impl<T: Clone + Copy, F: Fn(T, T) -> T + Copy> SparseTable<T, F>

pub fn new(a: &[T], op: F) -> Self

Build a Sparse Table from a slice using the given operation op, which must be associative and idempotent.

pub fn query(&self, l: usize, r: usize) -> Option<T>

Query op(a[l], a[l+1], ..., a[r-1]) over the half-open range [l, r). Returns None if the range is empty or out of bounds.

Two windows of length 2^k, where k = log2(r - l), exactly cover [l, r). Since op is idempotent, overlapping them is safe.