[][src]Crate prefix_sum

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.



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.



Data type allowing O(1) interval modifications to an array.