FenwickTreeLibrary

​

Design Characteristics

• O(log n) complexity for both updates and prefix sum queries.
• Storage-efficient using a mapping(uint256 => int256), instead of an array.
• Only supports lengths that are exact powers of two (2^k), which simplifies internal logic and allows future extensions via extend().

​

Invariants and Constraints

• The tree must be initialized with a power-of-two length > 0 via initialize(...).
• Index bounds are enforced — access beyond the current capacity reverts with IndexOutOfBounds().
• To support dynamic resizing, extend() can double the current tree length (up to a safe limit).
• Use of negative values is supported in modify(...), allowing decrement operations.

​

Data Structures

struct Tree {
    mapping(uint256 index => int256) _values; // Internal Fenwick Tree nodes.
    uint256 _length;                          // Capacity of the tree (must be power of two).
}

​

Functions

​

initialize(Tree storage tree, uint256 length_)

• Reverts with InvalidLength() if length_ == 0 or not a power of two.
• Only callable once (re-initialization is not allowed).

​

length(Tree storage tree) → uint256

​

extend(Tree storage tree)

• Preserves prefix sum structure.
• Reverts with InvalidLength() on overflow.

​

modify(Tree storage tree, uint256 index, int256 value)

• Performs tree[index] += value.
• Reverts if index is out of bounds.
• No-op if value == 0.

​

get(Tree storage tree, uint256 index) → int256

• If index >= length, it is clamped to length - 1.

​

get(Tree storage tree, uint256 from, uint256 to) → int256

• Returns 0 if from > to.

​

Internals

​

_modify(...)

• Updates tree[index] and propagates changes upward via index |= index + 1.

​

_get(...)

• Aggregates values by descending via index := and(index, index + 1) - 1.

​

References

• CP Algorithms: Fenwick Tree
• Wikipedia: Binary Indexed Tree