Fenwick Tree Structure

A Fenwick Tree uses 1-based indexing. Position $i$ stores the sum of elements from $i - \text{lowbit}(i) + 1$ to $i$.

Index (binary):  1(1)  2(10)  3(11)  4(100)  5(101)  6(110)  7(111)  8(1000)
Stores sum of:   [1]   [1,2]   [3]   [1-4]    [5]    [5,6]    [7]    [1-8]

Position $1$ stores $1$ element (lowbit = 1).

Position $2$ stores $2$ elements (lowbit = 2).

Position $4$ stores $4$ elements (lowbit = 4).

Position $8$ stores $8$ elements (lowbit = 8).

Each position covers a different "responsibility range." Together, they allow computing any prefix sum in $O(\log n)$ additions.