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 += 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
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
Types for slices of a
Prefix sums, but in two dimensions.
Traits for types that can be used in a
Data type allowing