This crate provides a trait,
CumlMap, representing a mapping between
keys and cumulative values. That is, an object implementing
should be able to store key-value mappings, and efficiently retrive
the sum of all values with a key less than or equal to a given key.
This crate also provides three implementations of the
FenwickTree is the most restricted in terms of what keys and values
it can accept, but also the most performant in those restricted cases.
FenwickTree accepts only non-negative keys, allocates all memory in
advance, and its capacity is fixed at creation time and
cannot be changed. If you need to get around any of these limitations
then use the
ExtensibleFenwickTree object instead.
ExtensibleFenwickTree may be a poor choice
for sparse keys. Both structures must allocate space for at least every
possible key between the smallest and largest keys. To get around this
limitation use the
CumlMap structure, which dynamically allocates
mappings, at the expense of insertion and lookup performance.
An extensible version of the Fenwick Tree.
A Fenwick Tree[^fn] structure, useful for very quickly mapping a non-negative integer key to a cumulative value.
Trait for building and querying mappings between keys and cumulative values.