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)
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.
```rust 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);
asserteq!(table.freq(0), 1); asserteq!(table.freq(3), 1); asserteq!(table.freq(5), 3); asserteq!(table.freq(6), 0);
asserteq!(table.sum(0), 1); asserteq!(table.sum(3), 2); asserteq!(table.sum(5), 5); asserteq!(table.sum(6), 5);
assert_eq!(table.total(), 5); ```
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.