# FenwickTreeLibrary

This library implements a **0-indexed** Fenwick Tree for tracking cumulative values over a dynamic array. It is suitable for systems where frequent prefix sum queries and point updates are required, such as time-based accounting, queuing systems, or share tracking.

### 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

```solidity
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_)`

Initializes the tree with the specified 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`

Returns the current capacity of the tree.

### `extend(Tree storage tree)`

Doubles the tree's capacity.

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

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

Increments or decrements the value at a given index by `value`.

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

### `get(Tree storage tree, uint256 index) → int256`

Returns the **prefix sum** for the range `[0, index]`.

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

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

Returns the sum over the range `[from, to]` (inclusive).

* Returns `0` if `from > to`.

### Internals

### `_modify(...)`

Low-level implementation of Fenwick update using bitwise operations:

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

### `_get(...)`

Assembly-optimized prefix sum computation:

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

### References

* [CP Algorithms: Fenwick Tree](https://cp-algorithms.com/data_structures/fenwick.html)
* [Wikipedia: Binary Indexed Tree](https://en.wikipedia.org/wiki/Fenwick_tree)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.mellow.finance/core-vaults/architecture/libraries/fenwicktreelibrary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.