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 and xor work 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.

The Rust crate lives at sparse_table/src/lib.rs; build & run it with:

$ cd sparse_table && cargo run
$ cd sparse_table && cargo test

Generated API reference for the Sparse Table crate. View the rendered API reference →

  1//! Sparse Table for idempotent range queries.
  2//!
  3//! A Sparse Table answers range queries on a static array in O(1) query
  4//! time after O(n log n) preprocessing, *as long as* the query operation
  5//! is idempotent and associative. The classic examples are `min`, `max`,
  6//! and `gcd`. (Sum works too; xor works too.)
  7//!
  8//! The trick: precompute `st[k][i] = op(a[i], a[i+1], ..., a[i+2^k-1])`
  9//! and overlap two intervals of length `2^k` to cover any range `[l, r]`.
 10//!
 11//! # Example
 12//!
 13//! ```
 14//! use sparse_table::SparseTable;
 15//!
 16//! let a = vec![1, 3, 2, 5, 4];
 17//! let st = SparseTable::new(&a, |x, y| if x < y { x } else { y });
 18//! assert_eq!(st.query(1, 4), Some(2)); // min over [1, 4) = min(3, 2, 5) = 2
 19//! assert_eq!(st.query(0, 5), Some(1)); // min over whole array
 20//! ```
 21
 22/// Sparse Table for idempotent, associative operations on a static array.
 23pub struct SparseTable<T, F: Fn(T, T) -> T> {
 24    /// `st[k][i]` holds the result of `op` over the half-open window
 25    /// `[i, i + 2^k)` of the original array.
 26    st: Vec<Vec<T>>,
 27    /// Precomputed floor(log2) values for fast index computation.
 28    log: Vec<usize>,
 29    /// The user-supplied operation, stored for use in queries.
 30    op: F,
 31}
 32
 33impl<T: Clone + Copy, F: Fn(T, T) -> T + Copy> SparseTable<T, F> {
 34    /// Build a Sparse Table from a slice using the given operation `op`,
 35    /// which must be associative and idempotent.
 36    pub fn new(a: &[T], op: F) -> Self {
 37        let n = a.len();
 38        if n == 0 {
 39            return SparseTable {
 40                st: Vec::new(),
 41                log: vec![0],
 42                op,
 43            };
 44        }
 45
 46        let max_k = (usize::BITS - n.leading_zeros()) as usize;
 47        let mut st: Vec<Vec<T>> = Vec::with_capacity(max_k);
 48        st.push(a.to_vec());
 49        for k in 1..max_k {
 50            let prev = &st[k - 1];
 51            // Row k has entries for windows [i, i + 2^k) with i + 2^k <= n,
 52            // so the count is n - 2^k + 1 (which is >= 1 because k < max_k).
 53            let len = n + 1 - (1 << k);
 54            let mut row: Vec<T> = Vec::with_capacity(len);
 55            for i in 0..len {
 56                row.push(op(prev[i], prev[i + (1 << (k - 1))]));
 57            }
 58            st.push(row);
 59        }
 60
 61        let mut log = vec![0usize; n + 1];
 62        for i in 2..=n {
 63            log[i] = log[i / 2] + 1;
 64        }
 65
 66        SparseTable { st, log, op }
 67    }
 68
 69    /// Query `op(a[l], a[l+1], ..., a[r-1])` over the half-open range
 70    /// `[l, r)`. Returns `None` if the range is empty or out of bounds.
 71    ///
 72    /// Two windows of length `2^k`, where `k = log2(r - l)`, exactly
 73    /// cover `[l, r)`. Since `op` is idempotent, overlapping them is
 74    /// safe.
 75    pub fn query(&self, l: usize, r: usize) -> Option<T> {
 76        let n = self.st.get(0).map(|v| v.len()).unwrap_or(0);
 77        if l >= r || r > n {
 78            return None;
 79        }
 80        let len = r - l;
 81        let k = self.log[len];
 82        let a = self.st[k][l];
 83        let b = self.st[k][r - (1 << k)];
 84        Some((self.op)(a, b))
 85    }
 86}
 87
 88/// Convenience constructor for `min` queries.
 89pub fn min_sparse_table(a: &[i64]) -> SparseTable<i64, fn(i64, i64) -> i64> {
 90    SparseTable::new(a, |x, y| if x < y { x } else { y })
 91}
 92
 93/// Convenience constructor for `max` queries.
 94pub fn max_sparse_table(a: &[i64]) -> SparseTable<i64, fn(i64, i64) -> i64> {
 95    SparseTable::new(a, |x, y| if x > y { x } else { y })
 96}
 97
 98/// Convenience constructor for `gcd` queries.
 99pub fn gcd_sparse_table(a: &[i64]) -> SparseTable<i64, fn(i64, i64) -> i64> {
100    SparseTable::new(a, |x, y| {
101        let (mut a, mut b) = (x.abs(), y.abs());
102        while b != 0 {
103            let t = b;
104            b = a % b;
105            a = t;
106        }
107        a
108    })
109}