Accumulation Tree
raw JSON → 0.6.4 verified Thu Apr 16 auth: no python
The `accumulation-tree` library provides a red/black tree data structure optimized for fast accumulation of values within a key range. It achieves O(log(N)) complexity for range aggregations by storing partial aggregations at each node, similar to a Fenwick tree. The current version is 0.6.4, and it is under active maintenance with releases occurring periodically to address compatibility and minor updates.
pip install accumulation-tree Common errors
error error: Microsoft Visual C++ 14.0 is required. Get it with "Build Tools for Visual Studio": https://visualstudio.microsoft.com/downloads/. ↓
cause The `accumulation-tree` library uses Cython, and building it from source on Windows requires a C++ compiler. Python often looks for Microsoft Visual C++.
fix
Download and install 'Build Tools for Visual Studio' from the provided URL, making sure to select the 'Desktop development with C++' workload during installation.
error ERROR: Failed building wheel for accumulation-tree ↓
cause This generic error often indicates a missing build dependency (like Cython itself) or a required compiler (like GCC, Clang, or MSVC) for compiling the Cython extensions.
fix
First, ensure
Cython is installed (pip install Cython). Then, verify that you have a suitable C/C++ compiler for your operating system (e.g., Build Tools for Visual Studio on Windows, build-essential on Debian/Ubuntu, Xcode Command Line Tools on macOS). Warnings
gotcha When installing `accumulation-tree` from source, especially on Windows, you might encounter build errors if a pre-compiled wheel is not available for your Python version and architecture. The package includes Cython code that requires a C compiler. ↓
fix Ensure you have a C compiler installed. On Windows, this typically means installing 'Build Tools for Visual Studio' (including the C++ build tools). On Linux/macOS, ensure `gcc` or `clang` is available.
deprecated During compilation, a warning 'Cython directive 'language_level' not set, using 2 for now (Py2). This will change in a later release!' may appear. This indicates that the Cythonized parts of the library are currently built with Python 2 compatibility in mind, which could lead to breaking changes in future versions if Python 2 support is fully dropped and the directive is enforced for Python 3. ↓
fix While this is a warning during compilation and not a runtime error, users should be aware that future versions might require re-compilation with an explicit `language_level=3` directive in the Cython source, which could affect compatibility with older Python 3 environments.
Imports
- AccumulationTree
from accumulation_tree import AccumulationTree
Quickstart
from accumulation_tree import AccumulationTree
# Initialize with an accumulation function (e.g., sum)
# The function `lambda x: x` means it accumulates the value itself.
# For a sum, this implies values are added up.
t = AccumulationTree(lambda x: x)
# Insert some values
N = 1000
for x in range(N):
t.insert(x, x) # insert key=x, value=x
# Get accumulation for a range (exclusive end key)
# accumulation for keys from 0 up to (but not including) 2
# This would be value at key 0 (0) + value at key 1 (1) = 1
print(f"Accumulation (0, 2): {t.get_accumulation(0, 2)}")
# accumulation for keys from 0 up to (but not including) 5
# This would be 0+1+2+3+4 = 10
print(f"Accumulation (0, 5): {t.get_accumulation(0, 5)}")
# Verify correctness for a larger range
# Sum of numbers from 0 to x-1 is x*(x-1)/2
all_correct = all(t.get_accumulation(0, x) == x * (x - 1) // 2 for x in range(N))
print(f"All accumulations correct up to {N-1}: {all_correct}")
# Get the full accumulated value of the tree
print(f"Total accumulation: {t.get_accumulation(t.min_key(), t.max_key() + 1)}")