competitive_programming_lib/DataStructures/
fenwick_tree.rs

1pub struct FenwickTree {
2    tree: Vec<i32>,
3}
4
5impl FenwickTree {
6    pub fn new(size: usize) -> Self {
7        FenwickTree {
8            tree: vec![0; size + 1],
9        }
10    }
11
12    pub fn update(&mut self, index: usize, value: i32) {
13        let mut index = index as isize;
14        while index < self.tree.len() as isize {
15            self.tree[index as usize] += value;
16            index += index & -index;
17        }
18    }
19
20    pub fn query(&self, index: usize) -> i32 {
21        let mut sum = 0;
22        let mut index = index as isize;
23        while index > 0 {
24            sum += self.tree[index as usize];
25            index -= index & -index;
26        }
27        sum
28    }
29
30    pub fn range_query(&self, left: usize, right: usize) -> i32 {
31        self.query(right) - self.query(left - 1)
32    }
33}