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.
void buildTree(vector<int> &arr, vector<int> &F, int n)
{
for(int i=1; i<=n; i++)
{
F[i] += arr[i];
if(i + (i & -i) <= n)
F[i + (i & -i)] += F[i];
}
}
Fenwick Tree (Binary Indexed Tree) for Competitive Programming
In the world of competitive programming, speed is everything. Fenwick Tree (also known as Binary Indexed Tree), created by Peter M. Fenwick. They’re like secret weapons for programmers, especially when you need to quickly find cumulative frequencies in problem-solving. This article breaks down Fenwick Trees in simple terms—how they’re built and why they’re handy for competitive programming. Whether you’re starting out or a pro looking for a speed boost, Fenwick Trees could be your key to success in coding competitions. Let’s dive in!