前缀和

此crate提供前缀和数据结构的实现。

用法

当您想要找到大量区间修改的组合结果时，可以使用此crate。

示例代码

use prefix_sum::PrefixSum;

let mut sum = PrefixSum::new(6);
// Each of these operations is O(1).
sum[2..4] += 2;
sum[1..3] += 3;
sum[0]    += 10;
sum[3..]  += 7;

// The build method is O(len).
assert_eq!(vec![10, 3, 5, 9, 7, 7], sum.build());

Cargo.toml

[dependencies]
prefix_sum = "0.1"

lib.rs:

此crate提供前缀和数据结构。

前缀和是一种数据结构，允许将多个区间修改累积并应用于数组。

use prefix_sum::PrefixSum;

let mut sum = PrefixSum::new(6);
// Each of these operations is O(1).
sum[2..4] += 2;
sum[1..3] += 3;
sum[0]    += 10;
sum[3..]  += 7;

// build is O(len).
assert_eq!(vec![10, 3, 5, 9, 7, 7], sum.build());

在PrefixSum中可用的类型是实现了Summable的类型。此特质对标准数字类型进行了实现，crate的各种特性使外类型也能实现。请参阅summable模块文档以获取这些特性的列表。

请注意，在前缀和中使用无符号类型需要包装减法和加法才能使用。

sum2d模块还提供了二维前缀和。