Prefix sum

This crate provides an implementation of the prefix sum data structure.

Usage

The use case of this crate is when you want to find the result of combining a large number of interval modifications.

Example code:

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:

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.