---
id: accumulation-tree
version: "0.6.4"
license: MIT License
license_treatment: permissive
maintenance: dormant
---

# accumulation-tree — Red/black tree with support for fast accumulation of values in a key range

License: permissive · Maintenance: dormant · Downloads: 231.5K/mo

## 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 above — 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

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

- License: MIT License (permissive)
- Python support: unspecified
- Install friction: high
- Maintenance: dormant
- Downloads: 231.5K/month (top 15,000 on PyPI)
- Known vulnerabilities: none known

## Tags

range sum query data structure, red black tree aggregation, fenwick tree alternative, fast range accumulation, BST with partial sums, key range slice queries, data-structures, range-queries

[View on SkillFed](https://skillfed.io/packages/accumulation-tree) · [View on PyPI](https://pypi.org/project/accumulation-tree/)