7 个版本 (3 个稳定版本)
| 2.0.1 | 2022年9月15日 |
|---|---|
| 2.0.0 | 2022年9月14日 |
| 1.0.0 | 2020年2月23日 |
| 0.2.0 | 2018年4月7日 |
| 0.1.2 | 2018年4月6日 |
#1728 在 数据结构 中
808 每月下载量
在 6 个 软件包中使用 （3 个直接使用）
15KB
173 行
Fenwick 树 或 二叉索引树/位索引树 是一种数据结构，它可以在数字数组上高效地支持以下两种操作：
- 计算前缀和：
a[0..n] - 更新一个元素：
a[i] += delta
在简单实现中，只有一个操作可以保证常数时间复杂度，而另一个操作必须是线性的。在 Fenwick 树中，两者都只需要 O(log(N))。
此软件包为 no_std 并且没有（非开发）依赖项。
示例
使用 array 模块对 1D Fenwick 树进行操作
use fenwick::array::{update, prefix_sum};
let fw = &mut [0i32; 10]; // backing array of Fenwick tree (NOT original array!)
assert_eq!(prefix_sum(fw, 0), 0);
assert_eq!(prefix_sum(fw, 9), 0);
update(fw, 0, 3); // original array: [3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 0), 3);
assert_eq!(prefix_sum(fw, 9), 3);
update(fw, 5, 9); // original array: [3, 0, 0, 0, 0, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), 3);
assert_eq!(prefix_sum(fw, 5), 12);
assert_eq!(prefix_sum(fw, 6), 12);
update(fw, 4, -5); // original array: [3, 0, 0, 0, -5, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), -2);
assert_eq!(prefix_sum(fw, 5), 7);
update(fw, 0, -2); // original array: [1, 0, 0, 0, -5, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), -4);
assert_eq!(prefix_sum(fw, 5), 5);
使用 index 模块实现多维 Fenwick 树
use fenwick::index::zero_based::{down, up};
const MAX: usize = 1000;
fn update(i: usize, j: usize, k: usize, delta: i32) {
for ii in up(i, MAX) {
for jj in up(j, MAX) {
for kk in up(k, MAX) {
/* increment 3D array at [ii, jj, kk] by delta */
}
}
}
}
fn prefix_sum(i: usize, j: usize, k: usize) -> i32 {
let mut sum = 0i32;
for ii in down(i) {
for jj in down(j) {
for kk in down(k) {
/* increment sum by 3D array at [ii, jj, kk] */
}
}
}
sum
}