competitive_programming_lib/DataStructures/
segment_tree.rs

1pub struct SegmentTree {
2    size: usize,
3    tree: Vec<i32>,
4}
5
6impl SegmentTree {
7    pub fn new(size: usize) -> Self {
8        let mut tree = vec![0; 2 * size];
9        SegmentTree { size, tree }
10    }
11
12    pub fn build(&mut self, data: &[i32]) {
13        for (i, &val) in data.iter().enumerate() {
14            self.tree[self.size + i] = val;
15        }
16
17        for i in (1..self.size).rev() {
18            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1];
19        }
20    }
21
22    pub fn query(&self, left: usize, right: usize) -> i32 {
23        let mut sum = 0;
24        let mut left = left + self.size;
25        let mut right = right + self.size;
26
27        while left <= right {
28            if left % 2 == 1 {
29                sum += self.tree[left];
30                left += 1;
31            }
32            if right % 2 == 0 {
33                sum += self.tree[right];
34                right -= 1;
35            }
36            left /= 2;
37            right /= 2;
38        }
39        sum
40    }
41}