The Fenwick Tree (FT) or Binary Indexed Tree (BIT) is an array built to store sums corresponding to another given array. The built array has the same size as the given array, and each position (or node) of the built array stores the sum of some elements of the given array. Since BIT stores partial sums of the given array, it is a very efficient solution for computing the sum of elements of the given array between two given indexes (range sum/queries) by avoiding looping between the indexes and computing the sum.
The BIT can be constructed in linear time or O(n log n). Obviously, we prefer it in linear time, so let's see how we can do this. We begin with the given (original) array that can be (the subscripts ...
