{"id":8805,"library":"accumulation-tree","title":"Accumulation Tree","description":"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.","status":"active","version":"0.6.4","language":"en","source_language":"en","source_url":"https://github.com/tkluck/accumulation_tree","tags":["data structure","red-black tree","range query","tree","accumulation","logarithmic","Cython"],"install":[{"cmd":"pip install accumulation-tree","lang":"bash","label":"Install latest stable version"}],"dependencies":[],"imports":[{"symbol":"AccumulationTree","correct":"from accumulation_tree import AccumulationTree"}],"quickstart":{"code":"from accumulation_tree import AccumulationTree\n\n# Initialize with an accumulation function (e.g., sum)\n# The function `lambda x: x` means it accumulates the value itself.\n# For a sum, this implies values are added up.\nt = AccumulationTree(lambda x: x)\n\n# Insert some values\nN = 1000\nfor x in range(N):\n    t.insert(x, x) # insert key=x, value=x\n\n# Get accumulation for a range (exclusive end key)\n# accumulation for keys from 0 up to (but not including) 2\n# This would be value at key 0 (0) + value at key 1 (1) = 1\nprint(f\"Accumulation (0, 2): {t.get_accumulation(0, 2)}\")\n\n# accumulation for keys from 0 up to (but not including) 5\n# This would be 0+1+2+3+4 = 10\nprint(f\"Accumulation (0, 5): {t.get_accumulation(0, 5)}\")\n\n# Verify correctness for a larger range\n# Sum of numbers from 0 to x-1 is x*(x-1)/2\nall_correct = all(t.get_accumulation(0, x) == x * (x - 1) // 2 for x in range(N))\nprint(f\"All accumulations correct up to {N-1}: {all_correct}\")\n\n# Get the full accumulated value of the tree\nprint(f\"Total accumulation: {t.get_accumulation(t.min_key(), t.max_key() + 1)}\")","lang":"python","description":"Demonstrates initializing an `AccumulationTree` with a simple summing function, inserting key-value pairs, and querying for the accumulated sum within specified key ranges."},"warnings":[{"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.","message":"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.","severity":"gotcha","affected_versions":"All versions when installing from source without a pre-built wheel."},{"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.","message":"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.","severity":"deprecated","affected_versions":"All versions including 0.6.4 (compilation warning)."}],"env_vars":null,"last_verified":"2026-04-16T00:00:00.000Z","next_check":"2026-07-15T00:00:00.000Z","problems":[{"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.","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++.","error":"error: Microsoft Visual C++ 14.0 is required. Get it with \"Build Tools for Visual Studio\": https://visualstudio.microsoft.com/downloads/."},{"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).","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.","error":"ERROR: Failed building wheel for accumulation-tree"}]}