fenwick-tree

Rust 中二叉索引树（或 Fenwick 树）数据结构的实现。

概述

fenwick-tree 提供了一个简单的 Fenwick 树实现，可以用作某些算法（如加权随机）的构建块。

基本 API 简单，包括 add 和 sum 方法（两者都为 O(log n) 时间）。以下是一个快速示例

use fenwick_tree::*;

let mut tree = FenwickTree::<i32>::with_len(5);

for i in 0..5 {
    tree.add(i, i as i32)?;
}

assert_eq!(tree.sum(..)?, 0 + 1 + 2 + 3 + 4);
assert_eq!(tree.sum(1..)?, 1 + 2 + 3 + 4);
assert_eq!(tree.sum(2..5)?, 2 + 3 + 4);
assert_eq!(tree.sum(3..=4)?, 3 + 4);

恐慌

add 和 sum 方法都返回 Result，并且不应该引发恐慌。然而，with_len 通过使用 vec![I::default(); len] 构建支持向量，实际上可能会像常规 Rust 代码一样引发恐慌。

了解更多

更多详细信息请参阅 文档。

许可证

该软件包采用 MIT 许可证。

贡献

对于贡献没有严格的规则。您可以随意提出问题或提交拉取请求。