Fenwick Tree? A Beautiful Data Structure!!!
More I look towards the logic behind this data structure more I get intrigued by it and then come to its implementation which sets the level of its own.
This is just an introductory explanation of the Fenwick tree with a simple example.
Introduction
Fenwick tree or Binary Indexed Tree is a data structure that can efficiently calculate prefix sums and update elements.
Basic idea
Each integer can be represented as a sum of powers of two. In the same way cumulative sum can be calculated as the sum of sets of this cumulative frequency.
Let the sum of sets of this cumulative frequency be represented by the array denoted by T.
T[4]=A[1]+A[2]+A[3]+A[4]
If you want to calculate the cumulative sum of A[1] to A[7] then
Cumulative Sum=T[7]+T[6]+T[4]{ T[7]=A[7], T[6]=A[6]+A[5], T[4]=A[1]+A[2]+A[3]+A[4]}
From where we get that T[7], T[6], and T[4] will contribute to prefix sum till 7?
7 is represented by 111 in binary. If you unset the last set bit then we get 110 which gives 6. Again if you unset the last set bit we get 100 which gives 4. So these are the indexes that contribute to prefix sum till 7.
How do we isolate the last set bit?
If “AND” the number with its two complements we get the last set bit of the number which we can subtract from the original number to unset the last set bit of the number. As shown in the image above 7 converted into 6 after unsetting the last set bit.
x-=(x&-x); //For unsetting the last bit which x goes to 0
Now the question comes where each number in the original array contributes in the array T.
Update
A[1] contributes to T[1],T[2],T[4],T[8] and so on{In binary 1->1,10,100,1000}
A[3] contributes to T[3],T[4],T[8] and so on{In binary 3->11,100,1000}
A[5] contributes to T[5],T[6],T[8] and so on{In binary 5->101,110,1000}
Here if we look closely then we can see we need to add last set bit to the number to go to the place where it will contribute next.
x+=(x&-x); //For adding the last set bit until x goes to the maximum length of the tree or original array.
Time Complexity
Space Complexity: O(N) for declaring another array of size N
Time Complexity:
O(log N) for each operation(update and query as well)
O(log N) for building the tree(n times updating the tree)
Example
Let's write some code for the range sum query using a Fenwick tree.
Updating the prefix sum tree
void update(int ind,int num){
while(ind<v.size()){
v[ind]+=num;
ind+=(ind & -ind); //Adding the last set bit
}
}Querying on the prefix sum tree
int getsum(int ind){ int sum=0;
while(ind>0){
sum+=v[ind];
ind-=(ind & -ind); //Unset the last set bit
}
return sum;
}
Building the tree
for(int i=0;i<n;i++){
int num;
cin>>num;
update(i+1,num);
}Getting Sum of range
while(t--){
int l,r;
cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<endl;
}Wrap up
The binary indexed tree is easy to implement and takes the linear amount of memory space. The query and update operation takes O(logN) time
Practice Problems
For practicing more problems on this amazing data structure.
