A leaner structure
A Fenwick tree, also called a binary indexed tree, supports prefix sums with point updates using just one array the same length as your data. It is smaller and simpler to code than a segment tree when you only need sums.
The clever indexing
Each index is responsible for a range of elements whose length is determined by the lowest set bit of that index. Index six in binary ends in a single set bit worth two, so position six stores the sum of the two elements ending there. This bit defines how far each cell reaches back.
Moving by the low bit
Two operations drive everything.
- To update a position, repeatedly add the low bit to the index, marching upward through every cell that includes that position.
- To query a prefix sum, repeatedly subtract the low bit from the index, hopping downward and accumulating partial sums.
The low bit of a number is isolated with the value and its two's complement negation, a tiny bit trick that powers the whole structure.
Why it is loved
The code is only a few lines, memory is a single array, and both operations stay logarithmic. For competitive sums and inversion counting it is often the first tool reached for.
Key idea
A Fenwick tree uses the lowest set bit of each index to march through cells, giving logarithmic prefix sums and point updates in one array.