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.

Modules

iter

Iterators over PrefixSum.

range

Types for slices of a PrefixSum.

sum2d

Prefix sums, but in two dimensions.

summable

Traits for types that can be used in a PrefixSum.

Structs

PrefixSum

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