Fenwick 树前缀和

功能说明

频繁单点更新又频繁区间求和的场景，普通数组更新是常数时间但求和是线性，前缀和数组求和是常数时间但更新要重建。Fenwick 树，也叫树状数组，把两者都降到对数时间：每个节点保存一段区间的和，节点覆盖的长度等于其下标的最低有效位。更新时不断加上最低有效位向上跳，查询时不断减去最低有效位向前跳。

本例用零基索引封装接口，内部数组多留一个位置。add 在指定下标增加一个值，prefix_sum 返回前 index 个元素之和，range_sum 用两个前缀和相减得到左闭右开区间。演示先构建数组，再查询两个区间，最后更新一个元素并重新查询。

关键代码

tree 长度为 size 加一，下标零不使用，使最低有效位运算更直观。add 先把外部零基下标转成一基，再循环累加，index & index.wrapping_neg() 取出最低有效位。prefix_sum 从一基下标开始，不断减去最低有效位并累加。range_sum 直接相减，左边界包含、右边界不包含。main 用带负数的数据验证，Fenwick 树同样支持负值。

使用注意

区间是左闭右开，调用时必须保证 left 小于等于 right 且不超过容量，否则会得到错误结果甚至越界。该实现只支持单点加法，若要区间加与区间求和，需要维护两个树或改用线段树。值是 64 位有符号整数，累加可能溢出，超大计数应评估上界或使用更大类型。wrapping_neg 在零下标上不会发生，但对外部传入越界索引没有防护。树不能动态扩容，容量需预先确定。

验证方式

运行脚本，前三行依次输出 15、15、25。第一个区间是前五个元素，第二个区间是下标三到七，更新在下标四增加十后，前五个元素之和从十五变为二十五。可把更新值改为负数，确认求和同步减少。

代码示例

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));
}