Idea behind Fenwick Trees

What is Fenwick Tree?

Fenwick Tree or Binary Indexed Tree is a data structure used to calculate range queries along with updating the elements of the array, such that each query or update takes logarithmic time complexity. It is used to calculate prefix sums or running total of values up to any index....

Why to use Fenwick Tree?

Whenever we have range queries along with updating the elements of the array such that the number of range queries are comparable to the number of updates in the array, then we can perform both of these operations in logarithmic time using Fenwick Trees....

Idea behind Fenwick Trees:

...

Fenwick Tree Implementation for Range Queries and Updates:

Since, we are storing Partial Sums of range in the Fenwick Tree F[], then updating an element at index i in the original array should reflect in all those indices of F[] which have index i in their partial sum range. For eg: if we want to update the element at index 5 in the original array, then it should reflect in F[5], F[6] and F[8] because F[5] stores the partial sum of range [5, 5], F[6] stores the partial sum of range [5, 6] and F[8] stores the partial sum of range [1, 8] and 5 lies in the range of all of them....

Building the Fenwick Tree in Linear Time Complexity:

In the above approach, we are building the Fenwick tree by calling the add() method for all the elements so the overall complexity to build the tree becomes O(N * logN). We can further reduce the time to build the Fenwick tree from O(N * logN) to O(N). Note that for every index i, we are adding a[i] to F[i], F[i + (i & (-i))] and so on. Also, later in the loop we have to add a[i + (i & (-i))] to all these indices again (except index i). So, instead of doing the operation repeatedly, we can combine them in one operation for every index. For every index i, we can simply add a[i] to F[i] and add F[i] to F[i + (i & (-i))]. Adding F[i] to F[i + (i & (-i))] will work same as adding a[i] to F[i + (i & (-i))] and all other indices....

Fenwick Tree (Binary Indexed Tree) for multi-dimensional arrays:

For 2-D arrays, we can use the same idea as 1-D array. Here, instead of storing Partial Sums of range [l to r], we store the Partial Sum of submatrix [l1 to r1][l2 to r2]. Refer this article to explore further about 2-D Fenwick Tree....

Use Cases of Fenwick Tree for Competitive Programming:

A Fenwick tree can support the following range operations:...

Practice Problems on Fenwick Tree for Competitive Programming:

Problem Problem Link Count Inversions Practice Now Easy Task Practice Now Array Partition Practice Now Range Minimum Query Practice Now Nitika and her queries Practice Now Maximum prefix sum for a given range Practice Now Smallest Subarray with given GCD Practice Now Element left after performing alternate OR & XOR operation Practice Now Easy Query Practice Now Akku and Arrays Practice Now Greater or Less Practice Now Sum and Update Queries on 3D Matrix in log(N) time Practice Now...