A space-efficient data structure for computing prefix sums and handling point updates.
A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for calculating prefix sums (the sum of elements from the start up to a given index) and updating element values in an array. Its primary advantage over a segment tree is its simplicity and significantly better space complexity—it only requires an array of the same size as the input array, O(n), whereas a segment tree needs up to 4n space. Both point updates and prefix sum queries can be performed in O(log n) time. The cleverness of the Fenwick tree lies in how it stores information. Each index `i` in the BIT stores the sum of a specific range of elements from the original array. The size of this range is determined by the last set bit in the binary representation of `i`. For example, `BIT[6]` (binary 110) would store `sum(arr[5], arr[6])`. To get a prefix sum up to an index `k`, we sum up `BIT[k]`, `BIT[k - LSB(k)]`, `BIT[k - LSB(k) - LSB(k-LSB(k))]`, and so on, where LSB is the least significant bit. This makes Fenwick trees extremely fast and useful for problems involving cumulative frequency or prefix sums.