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
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
115
116
117
118
119
120
121
122

use crate::{
    fenwick_tree_dual_with_instance_commutative_monoid::*,
    fenwick_tree_with_instance_abelian_group_1_indexed::*,
    fenwick_tree_with_instance_commutative_monoid_1_indexed::*,
};

impl<G: AbelianGroup> From<(G, &[G::T])> for DualFenwick<G>
where
    G::T: Clone,
{
    fn from(p: (G, &[G::T])) -> Self {
        let (g, data) = p;

        let mut data = data.to_vec();

        for i in (1..data.len()).rev() {
            data[i] = g.op(g.inv(data[i - 1].clone()), data[i].clone());
        }

        Self(Fenwick::from((g, data.as_slice())))
    }
}

impl<G: AbelianGroup> DualFenwick<G>
where
    G::T: Clone,
{
    pub fn operate(
        &mut self,
        l: usize,
        r: usize,
        x: G::T,
    ) {
        assert!(l < r && r <= self.size());

        if r < self.size() {
            self.operate_ge(r, self.0.g.inv(x.clone()));
        }

        self.operate_ge(l, x);
    }

    pub fn binary_search_from<F>(
        &self,
        is_ok: F,
        l: usize,
    ) -> usize
    where
        F: Fn(&G::T) -> bool,
    {
        assert!(l <= self.size());

        let prod_lt = if l == 0 { self.0.g.e() } else { self.get(l - 1) };

        self.0.max_right_from(
            &|prod_ge: &G::T| {
                !is_ok(&self.0.g.op(prod_lt.clone(), prod_ge.clone()))
            },
            l,
        )
    }
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        #[derive(Debug, Clone)]

        struct G;

        impl Monoid for G {
            type T = i32;

            fn e(&self) -> Self::T {
                0
            }

            fn op(
                &self,
                l: Self::T,
                r: Self::T,
            ) -> Self::T {
                l + r
            }
        }

        impl AbelianGroup for G {
            fn inv(
                &self,
                x: Self::T,
            ) -> Self::T {
                -x
            }
        }

        let a = vec![0, 1, 0, 0];

        let n = a.len();

        let mut fw = DualFenwick::from((G {}, a.as_slice()));

        for i in 0..n {
            assert_eq!(fw.get(i), a[i]);
        }

        fw.operate(2, 3, 1);

        for i in 0..n {
            assert_eq!(fw.get(i), a[i] + if i == 2 { 1 } else { 0 });
        }

        assert_eq!(fw.binary_search_from(|v| v <= &0, 1), 3);

        assert_eq!(fw.binary_search_from(|v| v <= &-1, 1), n);
    }
}