cuml_map

该库的目标是提供允许高效创建和查询累积映射的数据结构。也就是说，对于某些映射 K -> V，我们希望用户能够快速高效地询问以下问题

1. 与键 k 关联的值是什么？
2. 与键 <= k 关联的所有值的总和是多少？
3. 第一个键 k，其所有值的总和 <= k 大于或等于某个值 v？

这些查询被抽象到 CumlMap 特质中，该特质的定义如下

pub trait CumlMap {
    type Key;
    type Value;
    fn insert(&mut self, Self::Key, Self::Value);
    fn get_cuml(&self, Self::Key) -> Self::Value;              // Question 2
    fn get_single(&self, Self::Key) -> Self::Value;            // Question 1
    fn get_quantile(&self, Self::Value) -> Option<Self::Key>;  // Question 3
}

此外，还提供了三种该特质的实现

1. FenwickTree 实现了一个非常高效的基于数组的映射¹，其中 Key=usize。
2. ExtensibleFenwickTree 实现了 (1) 的包装，允许其动态调整大小，并接受可能为负的键。
3. CumlTree 使用基于红黑树的结构来泛化到任何有序键，对于稀疏键，它将比其他两个更加节省空间。

¹ Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables" (PDF). Software: Practice and Experience. 24 (3): 327–336. CiteSeerX 10.1.1.14.8917 Freely accessible. doi:10.1002/spe.4380240306