A Fenwick tree or binary indexed tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values. It was proposed by Peter Fenwick in 1994. Fenwick trees primarily solve the problem of balancing prefix sum calculation efficiency with element modification efficiency. The efficiency of these operations comes as a trade-off - greater efficiency in prefix sum calculation is achieved by pre-calculating values, but as more values are pre-calculated more must be re-calculated upon any modification to the underlying value table. Fenwick trees both calculate prefix sums and modify the table in time, where is the size of the table.