A Python library that implements Fenwick trees, based on the algorithm in (Fenwick 1994).
- Update a frequency in
O(log n). - Retrieve a single frequency in
O(log n). - Initialize existing frequencies in
O(n). - Retrieve all frequencies in
O(n).
fenwick supports python>=3.6.
Linux, Mac, and Windows are supported.
fenwick is available on PyPI, the Python Package Index.
$ pip install fenwick
See documentation.md.
See example.py.
Tests are in tests/.
# Run tests $ python -m unittest discover tests -v
The code in this repository has an MIT License.
See LICENSE.
Fenwick, Peter M. 1994. “A New Data Structure for Cumulative Frequency Tables.” Software: Practice and Experience 24 (3): 327–36.