Accumulation Tree

Common errors

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

Install

• pip install accumulation-tree Install latest stable version

Imports

• AccumulationTree

  from accumulation_tree import AccumulationTree

Quickstart

Demonstrates initializing an `AccumulationTree` with a simple summing function, inserting key-value pairs, and querying for the accumulated sum within specified key ranges.

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)}")