dsalgo 0.3.10

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

//! static range query for group like.

use crate::algebraic_structure::*;

pub struct CumulativeArray<G: Monoid> {
    s: Vec<G::S>,
}

impl<G: Monoid> CumulativeArray<G>
where
    G::S: Clone,
{
    pub fn new(mut a: Vec<G::S>) -> Self {
        let size = a.len();

        let mut s = vec![G::e()];

        s.append(&mut a);

        for i in 0..size {
            s[i + 1] = G::op(s[i].clone(), s[i + 1].clone());
        }

        Self { s }
    }

    pub fn size(&self) -> usize {
        self.s.len() - 1
    }

    pub fn reduce_lt(
        &self,
        i: usize,
    ) -> G::S {
        self.s[i].clone()
    }

    pub fn reduce(
        &self,
        l: usize,
        r: usize,
    ) -> G::S
    where
        G: Group,
    {
        assert!(l < r && r <= self.size());

        G::op(G::inv(self.reduce_lt(l)), self.reduce_lt(r))
    }
}

// TODO:
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}