A compact prefix sum tool
A Fenwick tree, also called a binary indexed tree, maintains prefix sums of an array with both point updates and prefix queries in logarithmic time. It uses a single flat array the same size as the input and almost no extra code, which makes it a favorite in contests.
The lowest set bit trick
The magic is the lowest set bit of an index, the value you get by combining an index with its negation in two's complement. Each position in the Fenwick array is responsible for a range of original elements whose length equals that lowest set bit.
- Query a prefix: start at the index and repeatedly subtract its lowest set bit, summing the values you pass, until you reach zero.
- Update a point: start at the index and repeatedly add its lowest set bit, adding the delta at each stop, until you pass the end.
Each loop runs once per set bit position, so both operations are logarithmic. A range sum comes from subtracting two prefix sums.
Key idea
By letting the lowest set bit define each cell's range, a Fenwick tree gives logarithmic prefix sums and updates with one array and a few lines of code.