binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.
In a flat array of n numbers, you can either store the elements, or the prefix sums.
In the first case, computing prefix sums requires linear time;
In the second case, updating the array elements requires linear time (in both cases, the other operation can be performed in constant time).
Fenwick trees allow both operations to be performed in O(log n) time. This is achieved by representing the numbers as a tree, where the value of each node is the sum of the numbers in that subtree.
