Rust语言树状数组实现方法（从零开始掌握Rust中的高效前缀和数据结构）

什么是树状数组？

树状数组并不是一棵真正的“树”，而是一种利用二进制特性对数组进行巧妙编码的数据结构。它的核心思想是：每个位置 i 存储一段区间的和，这个区间的长度由 i 的二进制最低位的 1 决定。

例如，对于索引 6（二进制为 110），其最低位的 1 对应的值是 2（即 2¹），因此 tree[6] 存储的是原数组中 [5, 6] 这两个元素的和。

Rust 实现树状数组的关键操作

在 Rust 中实现树状数组，我们需要两个核心函数：

• update(i, delta)：在原数组第 i 个位置加上 delta
• prefix_sum(i)：查询原数组前 i 项的和

注意：树状数组通常使用 1-based indexing（从 1 开始编号），这能简化二进制操作。

完整 Rust 代码实现

下面是一个完整的、可运行的 Rust 树状数组 实现：

pub struct FenwickTree {    tree: Vec<i32>,    n: usize,}impl FenwickTree {    // 创建一个新的树状数组，初始大小为 n    pub fn new(n: usize) -> Self {        FenwickTree {            tree: vec![0; n + 1], // 使用 1-based 索引，所以分配 n+1 个元素            n,        }    }    // 获取 i 的最低位 1 所代表的值（lowbit）    fn lowbit(x: usize) -> usize {        x & (!x + 1)    }    // 在位置 i 增加 delta（i 从 1 开始）    pub fn update(&mut self, i: usize, delta: i32) {        let mut idx = i;        while idx <= self.n {            self.tree[idx] += delta;            idx += Self::lowbit(idx);        }    }    // 查询前缀和 [1, i]    pub fn prefix_sum(&self, i: usize) -> i32 {        let mut sum = 0;        let mut idx = i;        while idx > 0 {            sum += self.tree[idx];            idx -= Self::lowbit(idx);        }        sum    }    // 查询区间 [l, r] 的和    pub fn range_sum(&self, l: usize, r: usize) -> i32 {        self.prefix_sum(r) - self.prefix_sum(l - 1)    }}

如何使用这个树状数组？

下面是一个简单的使用示例：

fn main() {    let mut ft = FenwickTree::new(5); // 支持 5 个元素    // 初始化数组 [1, 2, 3, 4, 5]    ft.update(1, 1);    ft.update(2, 2);    ft.update(3, 3);    ft.update(4, 4);    ft.update(5, 5);    println!("前缀和 [1..3]: {}", ft.prefix_sum(3)); // 输出 6    println!("区间和 [2..4]: {}", ft.range_sum(2, 4)); // 输出 9    // 更新第 3 个元素 +10    ft.update(3, 10);    println!("更新后前缀和 [1..3]: {}", ft.prefix_sum(3)); // 输出 16}

为什么选择 Rust 实现树状数组？

Rust 提供了内存安全、零成本抽象和高性能的特性，非常适合实现底层数据结构。通过 Vec 和所有权机制，我们可以写出既安全又高效的 树状数组实现，避免空指针或越界错误。

此外，Rust 的编译器会在编译期检查所有边界条件，让你在开发阶段就能发现潜在问题，这对于处理像 二叉索引树 这类依赖精确索引逻辑的数据结构尤为重要。

总结

通过本文，你已经掌握了如何在 Rust 中实现并使用树状数组。无论是用于解决 LeetCode 题目，还是在实际项目中优化前缀和计算，这套 Rust 数据结构 实现都能为你提供强大支持。

记住关键点：使用 1-based 索引、理解 lowbit 操作、掌握 update 和 prefix_sum 的循环逻辑。多加练习，你很快就能熟练运用这一高效工具！

关键词回顾：Rust树状数组、树状数组实现、Rust数据结构、二叉索引树Rust。