How a Fenwick tree (binary indexed tree) works
A Fenwick tree, also called a binary indexed tree (BIT), stores cumulative information in a single array so that prefix sums and point updates both run in O(log n) time. Each index i is responsible for a range of elements whose length equals the value of the lowest set bit of i, written i and (-i) in two's complement arithmetic. This low-bit decomposition is what lets the structure walk the array in logarithmic steps rather than linear ones.
To query a prefix sum up to index i, you repeatedly add the value at i and then strip its lowest set bit until you reach zero. To update an element, you move in the opposite direction, adding the low bit each step.
Where it is used
Fenwick trees are common in competitive programming and in systems needing frequent range-sum queries with updates, such as counting inversions, dynamic frequency tables, and order statistics. Compared with a segment tree, a BIT uses less memory and has shorter code, but it natively supports only invertible operations like sums; a segment tree is more flexible for operations like minimum or maximum. A range sum from l to r is computed as prefix(r) minus prefix(l-1).