CumulFreqTable

使用二叉索引树在数组中存储累积频率。

就像一个整数是适当的二的幂的和一样，累积频率也可以表示为适当的一组累积子频率的和。参见 Peter M. Fenwick 的 "A New Data Structure for Cumulative Frequency Tables." (1994)

定义

累积频率表存储和/或计算表中每个位置的绝对频率和累积频率。

来自 Wikipedia 的正式定义

在统计学中，事件 i 的频率（或绝对频率）是观察值在实验或研究中发生/记录的次数 nᵢ。累积频率是在有序事件列表中或低于一定点的所有事件的绝对频率的总和。

示例

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);

实现

此crate提供对[CumulFreqTable] trait的两个实现

• [FreqTable]：以O(1)的时间复杂度存储每个位置的绝对频率，但以O(len)的时间复杂度计算累积频率。适用于小型表格。
• [BinaryIndexedTree]：在二叉索引树中存储每个位置的累积频率。所有操作的运行时间复杂度都是O(㏒₂ len)。