atcoder_fenwick.rs

mod fenwick{
    pub struct Fenwick{
        data: Vec<i64>,
        n_leaves: usize
    }

    impl Fenwick{
        pub fn new(n: usize) -> Self{
            // n以上の最小の2羃をさがす
            let n_leaves = (0..).map(|i| 2usize.pow(i)).find(|&i| {i >= n}).unwrap();
            Fenwick{
                data: vec![0; n_leaves*2],
                n_leaves: n_leaves
            }
        }

        fn add_help(&mut self, val: i64, pos: usize){
            if pos == 0{
                return;
            }

            self.data[pos] += val;
            self.add_help(val, pos/2);
        }

        pub fn add(&mut self, val: i64, pos: usize){
            self.add_help(val, pos + self.n_leaves);
        }

        fn get_help(&self, b: usize, u: usize, k: usize, l: usize, r: usize) -> i64{
            if r <= b || u <= l{
                return 0; // disjoint
            }

            if b <= l && r <= u{
                return self.data[k];
            }

            return self.get_help(b, u, 2*k, l, (l+r)/2) + self.get_help(b, u, 2*k+1, (l+r)/2, r);
        }

        pub fn get(&self, b: usize, u: usize) -> i64{
            return self.get_help(b, u, 1, 0, self.n_leaves);
        }
    }
}