fenwick

A Python library that implements Fenwick trees, based on the algorithm in (Fenwick 1994).

Features

• 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).

Requirements

fenwick supports Python 2.7 and Python 3.x.

Linux, Mac, and Windows are supported.

Installation

fenwick is available on PyPI, the Python Package Index.

$ pip install fenwick

Documentation

See documentation.md.

Example Usage

See example.py.

Tests

Tests are in tests/.

# Run tests
$ python -m unittest discover tests -v

License

The code in this repository has an MIT License.

See LICENSE.

References

Fenwick, Peter M. 1994. “A New Data Structure for Cumulative Frequency Tables.” Software: Practice and Experience 24 (3): 327–36.