accumulation-tree

What it is and what it does

AccumulationTree is a red/black binary search tree variant that maintains partial aggregations (sums, products, or other reductions) at each node. This design allows range queries—asking for the accumulated value across all keys between two bounds—to complete in O(log N) time instead of requiring a linear scan. The package is similar in purpose to a Fenwick tree but uses explicit heap-allocated nodes rather than an implicit array-based structure.

The package was originally written for use in tdigest and borrows implementation details from bintrees. It accepts a user-supplied aggregation function (e.g., `lambda x: x` for summation) and supports insertion and range accumulation queries. No external runtime dependencies are required, making it a lightweight addition to projects that need fast range aggregations on sorted data.

Use it for:

• Computing cumulative sums over ranges of time-series data in O(log N) time
• Building digest or histogram structures that need efficient percentile or range-based statistics
• Implementing range queries in sorted key-value stores without scanning all intermediate values
• Aggregating metrics or measurements across time windows in monitoring or analytics pipelines

Worth the install?

AI-flagged interpretation of the facts on this page — verify before relying

Implements a red/black tree that stores partial aggregations at each node, enabling O(log N) range sum queries on sorted key-value pairs.

Yes, if you need fast range aggregations on sorted data and are comfortable with high install friction from a source distribution. The dormant maintenance status (last release 687 days ago) and lack of active development are acceptable for a stable, narrow-purpose data structure with no known vulnerabilities, but expect no updates or support for new Python versions.

Install

accumulation-tree on PyPI

pip install accumulation-tree

uv add accumulation-tree

poetry add accumulation-tree

Installing accumulation-tree

Before you install

High install friction from a source distribution with no runtime dependencies. Maintenance is dormant—last release was 687 days ago, though the repository remains active with a recent commit on 2024-09-26.

License in practice

MIT License (permissive) places no restrictions on use, modification, or distribution in commercial or private projects.

Quickstart

from accumulation_tree import AccumulationTree
t = AccumulationTree(lambda x: x)
for x in range(10000):
    t.insert(x, x)
result = t.get_accumulation(0, 5)

Source distribution (.tar.gz); may require a C compiler and build tools to install.

Verify before relying

• Whether the package requires a C compiler or build tools to install from source
• Actual Python version compatibility beyond the classifiers (2 and 3 listed but requires_python unspecified)
• Performance characteristics and memory overhead compared to alternatives like Fenwick trees

Package facts

Evidence: accumulation_tree-0.6.4.tar.gz

Keywords: BST, data structure, accumulation

Tags

More Scientific/Engineering packages