accumulation-tree

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