sparse_table/
lib.rs

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}
sparse_table/lib.rs

sparse_table/
lib.rs
