Arrays operations, such as calculating prefix sums of array elements normally done at a linear time – 0(n). In most cases, linear time for such operations is good enough, but sometimes linear time operations can become very costly. This is where the Fenwick tree comes in handy.
The following materials are based on several resources, such as the Wikipedia article, and the article by Peter M. Fenwick.
What is Fenwick Tree?
A method for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions that parallel the binary representation of the index of the array element. Accessing and manipulating the array elements is done based on the binary coding of the element index. The Fenwick tree allows accessing and updating arrays’ elements at a constant or logarithm time of the array length. That means operations on large arrays can significantly improve performance by implementing the Fenwick tree.
Fenwick Tree’s Principles
The basic idea is that, just as an integer is the sum of appropriate powers of two,
Peter M. Fenwick 1994
so can a cumulative frequency be represented as the appropriate sum of sets of
cumulative ‘subfrequencies’. Thus, if the index contains a ‘2 bit’ we include two
frequencies, if it has an ‘8 bit’ we include 8 frequencies, and so on.
Although the concept of Fenwick tree is a tree of array frequencies, in practice it is implemented as an implicit data structure. Given an index in the array representing a vertex, the index of a vertex’s parent/child is calculated through bitwise operations on the binary representation of its index.
Each element of the array contains the pre-calculated sum of a range of values. By combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all range sums that contain the modified value are in turn modified during a similar traversal of the tree. The range sums are defined such that both queries and modifications to the table are executed in asymptotically equivalent time (0(log n) in the worst case).
The initial process of building the Fenwick tree over a table of values runs in O(n) time. Other efficient operations include locating the index of a value if all values are positive. Or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in O(n) time.