Lib.rs

略微过度设计的 Fenwick Tree 实现。

允许高效的前缀和计算。

为培训目的创建，以测试

1. rust 类型系统、默认特质的实现、枚举作为多态的方式
2. 内存管理和值消耗
3. cargo 工具、文档、测试、clippy 和基准测试、构建和发布。

代码可自由进行任何操作。

为 Fenwick 树数据结构及其 2 个实现提供抽象

• 预定义::FixedSizeFenwickTree
• 预定义::GrowingFenwickTree

树的关键空间位于 usize 范围内。树支持任何实现了 FenwickTreeValue 特质的值。所有支持 std::ops::AddAssign、std::ops::Sub、core::cmp::PartialEq 和 Copy 特质的原始数值类型都会自动实现 FenwickTreeValue。

安装

cargo add fenwick-bit-tree

测试

cargo test

基准测试

cargo bench --features benchmarks

基本用法

use fenwick_bit_tree::prelude::*;

// Create the tree with capacity for 32 aggregated [`i32`] data points.
// One can use whole usize range to store datapoints for unicode timestamps
let mut tree = FixedSizeFenwickTree::<i32>::new(32);

// Add values

tree.update(0, 1);
tree.update(0, 4); // Will aggregate value at index 0 so it would be 5
tree.update(10, 10);
tree.update(20, 10);
tree.update(30, 10);

// Now you can query data.
// NOTE: FixedSizeFenwickTree will raise error when query goes out of bounds.
//       GrowingFenwickTree will automatically truncate the range to the rightmost index.

assert_eq!(tree.query(4).unwrap(), 5);
assert_eq!(tree.query(15).unwrap(), 15);
assert_eq!(tree.query(31).unwrap(), 35);

// Also allows making range queries

let val = tree.range_query(2, 16).unwrap(); // Will return aggregated sum of all values between those keys.
assert_eq!(val, 10);

当前版本：2.0.2

许可证：MIT OR Apache-2.0