A Fenwick tree or 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. When compared with a flat array of numbers, the Fenwick tree achieves much higher performance for two operations: element update and prefix sum calculation. In a flat array of numbers, calculating prefix sum and updating the elements both require time. Fenwick trees allow both operations to be performed in node accesses.