中文
devexamples

Fenwick Tree Prefix Sums

Support point updates and range-sum queries in logarithmic time with a compact binary indexed tree and low-bit navigation.

RustData Integrity

Code

snippet
struct Fenwick {
    tree: Vec<i64>,
}

impl Fenwick {
    fn new(size: usize) -> Self {
        Self {
            tree: vec![0; size + 1],
        }
    }

    fn add(&mut self, mut index: usize, delta: i64) {
        index += 1;
        while index < self.tree.len() {
            self.tree[index] += delta;
            index += index & index.wrapping_neg();
        }
    }

    fn prefix_sum(&self, mut index: usize) -> i64 {
        let mut total = 0;
        while index > 0 {
            total += self.tree[index];
            index -= index & index.wrapping_neg();
        }
        total
    }

    fn range_sum(&self, left: usize, right: usize) -> i64 {
        self.prefix_sum(right) - self.prefix_sum(left)
    }
}

fn main() {
    let values = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3];
    let mut tree = Fenwick::new(values.len());
    for (index, value) in values.iter().enumerate() {
        tree.add(index, *value);
    }
    println!("sum 0..5 = {}", tree.range_sum(0, 5));
    println!("sum 3..8 = {}", tree.range_sum(3, 8));
    tree.add(4, 10);
    println!("after update 0..5 = {}", tree.range_sum(0, 5));
}

Related Examples