dsalgo 0.2.6

A package for Datastructures and Algorithms.
Documentation 
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

use crate::{abstract_structs, bitset};

pub struct SparseTable<'a, S> {
    sg: abstract_structs::Semigroup<'a, S>,
    data: Vec<Vec<S>>,
}

impl<'a, S: Default + Clone> SparseTable<'a, S> {
    pub fn new(sg: abstract_structs::Semigroup<'a, S>, a: &Vec<S>) -> Self {
        assert!(sg.idempotent && sg.commutative);
        let n = a.len();
        assert!(n > 0);
        let k = std::cmp::max(1, bitset::bit_length(n - 1));
        let mut data = vec![vec![S::default(); n]; k];
        data[0] = a.clone();
        for i in 0..k - 1 {
            data[i + 1] = data[i].clone();
            for j in 0..n - (1 << i) {
                data[i + 1][j] =
                    (sg.operate)(&data[i][j], &data[i][j + (1 << i)])
            }
        }
        Self {
            sg: sg,
            data: data,
        }
    }

    pub fn get(&self, l: usize, r: usize) -> S {
        assert!(l < r && r <= self.data[0].len());
        if r - l == 1 {
            return self.data[0][l].clone();
        }
        let k = bitset::bit_length(r - 1 - l) - 1;
        (self.sg.operate)(&self.data[k][l], &self.data[k][r - (1 << k)])
    }
}

pub struct DisjointSparseTable<'a, S> {
    sg: abstract_structs::Semigroup<'a, S>,
    data: Vec<Vec<S>>,
}

impl<'a, S: Default + Clone> DisjointSparseTable<'a, S> {
    pub fn new(sg: abstract_structs::Semigroup<'a, S>, a: &Vec<S>) -> Self {
        let n = a.len();
        assert!(n > 0);
        let k = std::cmp::max(1, bitset::bit_length(n - 1));
        let mut data = vec![vec![S::default(); n]; k];
        data[0] = a.clone();
        for i in 1..k {
            data[i] = a.clone();
            for j in (1 << i..n + 1).step_by(2 << i) {
                for k in 1..(1 << i) {
                    data[i][j - k - 1] =
                        (sg.operate)(&data[i][j - k - 1], &data[i][j - k]);
                }
                for k in 0..(1 << i) - 1 {
                    if j + k + 1 >= n {
                        break;
                    }
                    data[i][j + k + 1] =
                        (sg.operate)(&data[i][j + k], &data[i][j + k + 1]);
                }
            }
        }
        Self {
            sg: sg,
            data: data,
        }
    }

    pub fn get(&self, l: usize, r: usize) -> S {
        assert!(l < r && r <= self.data[0].len());
        if r - l == 1 {
            return self.data[0][l].clone();
        }
        let k = bitset::bit_length(l ^ (r - 1)) - 1;
        (self.sg.operate)(&self.data[k][l], &self.data[k][r - 1])
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sparse_table() {
        let sg = abstract_structs::Semigroup::<i64> {
            operate: &|x, y| std::cmp::min(*x, *y),
            commutative: true,
            idempotent: true,
        };
        let a = vec![0, 4, 2, 8, 5, 1];
        let sp = SparseTable::new(sg, &a);
        assert_eq!(sp.get(0, 4), 0);
        assert_eq!(sp.get(3, 4), 8);
        assert_eq!(sp.get(1, 6), 1);
    }

    #[test]
    fn test_disjoint_sparse_table() {
        let sg = abstract_structs::Semigroup::<i64> {
            operate: &|x, y| std::cmp::min(*x, *y),
            commutative: true,
            idempotent: true,
        };
        let a = vec![0, 4, 2, 8, 5, 1];
        let sp = DisjointSparseTable::new(sg, &a);
        assert_eq!(sp.get(0, 4), 0);
        assert_eq!(sp.get(3, 4), 8);
        assert_eq!(sp.get(1, 6), 1);
    }
}