Binary Indexed Tree | Jes2ica.IO

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.

Problem

1. add marble to box i
2. sum marbles from box k to box l

Naive Solution

Idea

Example

Applications

• Range Sum Query - Mutable

More info:

• Topcoder