1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

//! SparseTable
//! 冪等半群列にたいして区間[l,r) の結果を戻す
//! 構築 O(NlogN) クエリO(1)
//! min, max, gcd, lcm 等

use std::ops::Range;

/// 冪等半群
pub trait Band {
    type T: Clone;
    fn operate(a: &Self::T, b: &Self::T) -> Self::T;
}

/// 最小値
pub struct Min {}
impl Band for Min {
    type T = i64;

    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
        *a.min(b)
    }
}

/// SparseTable
pub struct SparseTable<B: Band> {
    table: Vec<Vec<B::T>>,
}

impl<B: Band> SparseTable<B> {
    /// O(NlogN)
    pub fn new(v: &[B::T]) -> Self {
        let mut table = vec![v.to_vec()];

        for i in 1..64 - v.len().leading_zeros() as usize {
            let mut tmp = vec![];
            for j in 0..=v.len() - (1 << i) {
                tmp.push(B::operate(
                    &table[i - 1][j],
                    &table[i - 1][j + (1 << (i - 1))],
                ));
            }
            table.push(tmp);
        }

        SparseTable { table }
    }

    /// [l,r)
    /// O(1)
    pub fn fold(&self, range: Range<usize>) -> B::T {
        let i = 64 - (range.end - range.start).leading_zeros() as usize - 1;
        B::operate(
            &self.table[i][range.start],
            &self.table[i][range.end - (1 << i)],
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_sparse_table() {
        let a = SparseTable::<Min>::new(&[2, 10, 1, 100]);
        for (l, r, ans) in [
            (0, 1, 2),
            (0, 2, 2),
            (0, 3, 1),
            (0, 4, 1),
            (1, 2, 10),
            (1, 3, 1),
            (1, 4, 1),
            (2, 3, 1),
            (2, 4, 1),
            (3, 4, 100),
        ]
        .iter()
        {
            assert_eq!(a.fold(*l..*r), *ans);
        }
    }
}