Every positive integer 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 stores the sum of a range whose length is the lowest set bit of . Example: position (binary ) stores sum of elements (lowest bit is ).
Position (binary ) stores sum of elements. Position (binary ) stores sum of element. To get prefix sum up to position :
Add tree[i]
Remove the lowest set bit from
Repeat until becomes This visits at most positions.