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

use crate::functional_graph_basic_properties::*;

pub struct PrefixSum {
    s: Vec<usize>,
    start: usize,
}

impl PrefixSum {
    pub fn new(
        f: &[usize],
        src: usize,
        a: &[usize],
    ) -> Self {
        let (nodes, start) = functional_graph_prop(f, src);

        let mut s: Vec<_> = nodes.into_iter().map(|i| a[i].clone()).collect();

        for i in 1..s.len() {
            if i == start {
                continue;
            }

            s[i] += s[i - 1];
        }

        Self { s, start }
    }

    /// 0-indexed

    pub fn calc(
        &self,
        mut k: usize,
    ) -> usize {
        let j = self.start;

        let s = &self.s;

        if k < j {
            return s[k];
        }

        let mut res = 0;

        let l = s.len() - j;

        if j > 0 {
            res = s[j - 1];

            k -= j;
        }

        res += k / l * s.last().unwrap();

        k %= l;

        res += s[j + k];

        res
    }
}