The Core Idea

Every positive integer $i$ you can write as a sum of distinct powers of 2 (its binary representation).

Fenwick Trees exploit this: instead of storing prefix sums directly, they store partial sums at strategic positions.

Position $i$ stores the sum of a range whose length is the lowest set bit of $i$. Example: position $12$ (binary $1100$) stores sum of $4$ elements (lowest bit is $100 = 4$).

Position $8$ (binary $1000$) stores sum of $8$ elements. Position $7$ (binary $111$) stores sum of $1$ element. To get prefix sum up to position $i$:

$1.$ Add tree[i]

$2.$ Remove the lowest set bit from $i$

$3.$ Repeat until $i$ becomes $0$ This visits at most $\log n$ positions.