CumulFreqTable

Store cumulative frequencies with a binary indexed tree in an array.

Just as an integer is the sum of appropriate powers of two, so can a cumulative frequency be represented as the appropriate sum of sets of cumulative sub-frequencies. from peter m. fenwick, "a new data structure for cumulative frequency tables." (1994)

Definition

A cumulative frequency table stores and/or compute the absolute frequency and the cumulative frequency for ever position in the table.

Formal definition from Wikipedia:

In statistics, the frequency (or absolute frequency) of an event i is the number nᵢ of times the observation has occurred/recorded in an experiment or study. The cumulative frequency is the total of the absolute frequencies of all events at or below a certain point in an ordered list of events.

Example

use cumulfreqtable::CumulFreqTable; // Import the trait in scope.

let mut table = cumulfreqtable::BinaryIndexedTree::new(16);
table.inc(0);
table.inc(3);
table.add(5, 3);

assert_eq!(table.freq(0), 1);
assert_eq!(table.freq(3), 1);
assert_eq!(table.freq(5), 3);
assert_eq!(table.freq(6), 0);

assert_eq!(table.sum(0), 1);
assert_eq!(table.sum(3), 2);
assert_eq!(table.sum(5), 5);
assert_eq!(table.sum(6), 5);

assert_eq!(table.total(), 5);

Implementations

This crate offers two implementations of the [CumulFreqTable] trait:

• [FreqTable]: stores the absolute frequency of every positions in an array O(1) but computes the cumulative frequency in O(len). Best for small tables.
• [BinaryIndexedTree]: stores the cumulative frequency of every positions in a binary indexed tree. The runtime complexity is O(㏒₂ len) for all operations.