Fenwick tree

A Fenwick tree, also called a binary indexed tree, is an array-backed data structure that maintains prefix sums as individual values change. Adding to one position and summing through any position each take $O(\log n)$ time in the worst case. For a fixed order-book price ladder, it lets a market-data process keep cumulative displayed ask depth current as orders arrive and cancel.

Number the levels from 1 through $n$ in ascending ask-price order. Let $a_i$ be the displayed shares at level $i$. The lowbit of $i$ is the value of its rightmost 1 bit, computed as i & -i. For instance, 6 is binary 110, so its lowbit is 2. Slot tree[6] stores the sum over levels 5 and 6. In general, slot $i$ stores the sum over a block of length $\operatorname{lowbit}(i)$ ending at $i$.

To read a prefix, start at its right endpoint. Take that slot's sum, subtract its lowbit from the index and repeat until zero. Each step jumps immediately to the left of the block just counted. To add to a single position, start there and add the change to that slot’s sum. Increase the index by its lowbit and repeat until it passes the last slot. This visits precisely the blocks that contain the changed position. The tree is implicit in these index steps. Zero represents the empty prefix and is never a valid update index. Fenwick’s original paper describes both walks.

Suppose the displayed shares in eight fictional ask levels are $(3,1,4,1,5,9,2,6)$. A request for the total through level 7 reads tree[7], tree[6] and tree[4]. Their blocks cover level 7, levels 5–6 and levels 1–4 respectively, for $2+14+9=25$ shares.

Now add 2 shares at level 3. The update follows $3\to4\to8$ and adds 2 to each of those slots. Only tree[4] lies on both walks. The same prefix query therefore gives $2+14+11=27$ shares.

With $S(k)$ the inclusive prefix through $k$ and $S(0)=0$, the sum from level $l$ through $r$ is $S(r)-S(l-1)$. Each prefix step clears a set bit. Each update step makes the lowbit at least twice as large until the index leaves the array. Both walks thus take at most logarithmically many steps, and the stored totals use $O(n)$ space. A static prefix-sum array answers range sums in $O(1)$ after construction, but a point change can invalidate every prefix ending at or after that position. For arbitrary interval minima or maxima under point updates, use a segment tree. Laaksonen compares these structures in Chapter 9.

The level-to-index mapping must stay stable while the tree is in use. Order priority at a single price requires order-level information. The SelfMadeQuant Order Books lesson uses cumulative depth to work through a hypothetical fill and explains what queue information matters for passive orders. The preview is public and the full lesson requires membership.