Crate prefix_sum
source ·Expand description
This crate provides the prefix sum data structure.
A prefix sum is a data structure allowing several interval modifications to be accumulated and applied to an array.
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());
The types usable in a PrefixSum
are those implementing Summable
. This trait
is implemented for the standard number types, and various features on the crate enable
implementations for various foreign types. See the summable
module
documentation for a list of these features.
Note that usage of unsigned types in a prefix sum requires wrapping subtraction and addition to be usable.
A two dimensional prefix sum is also provided in the sum2d
module.
Modules
Iterators over
PrefixSum
.Types for slices of a
PrefixSum
.Prefix sums, but in two dimensions.
Traits for types that can be used in a
PrefixSum
.Structs
Data type allowing
O(1)
interval modifications to an array.