Fenwick Tree(Binary Indexed Tree) Explained

This article introduces the basic principles and implementation methods of Fenwick Tree (Binary Indexed Tree).

Fenwick tree, also called a binary indexed tree (or just BIT abbreviated), is a tree data structure that can efficiently update elements and calculate range sums on a list of numbers.

Fenwick tree was first described in a paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).