ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

Tree data structure tutorial 14. Fenwick trees and implementation

prodevelopertutorial August 18, 2019

Introduction to Fenwick tree or Binary Indexed Tree.

 

In this tutorial we shall lean to perform

  1. Get range sum
  2. Update range

by using Fenwick tree.

 

Problem Statement:

Given an array you need to find the sum of ranges.

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

We need to find the sum for the range [ 0 – 3].

2 + 3 + 1 + 5 = 11.

The simple way to do it by using brute force approach. i.e to add all the elements from the starting index to ending index.

It will take linear amount of time.

 

Is there any other method to solve this problem?

Yes, take another array where you can store the sum of previous index elements.

 

For example:

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

But there is a problem here. What if you update the value at index 2, to add “1” to it?

 

Then you need to add “1” to all the elements after index 2

Tree data structure tutorial 14. Fenwick trees and implementation

 

But if you update at the index ‘0’, then it will take O(n) time to update all the values.

 

Is there any other efficient method to solve it?

 

Yes, we can use Fenwick tree.

 

Fenwick tree is based on the fact that all the numbers can be represented by 2^n. Hence the algorithm will take advantage of this to make queries faster.

 

We shall understand Fenwick tree with help of an example.

 

Fenwick tree will be useful for 2 operations. These operations we shall see in this chapter also.

 

  1. Compute the sum when given a range
  2. Add a value an element given an index

 

Consider the array with 14 elements as below:

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

  1. Computer the sum when given a range

 

For example we need to find sum(13).

As we said above, any number can be represented with power of 2.

 

13 can be written as 2^3 + 2^2 + 2^0

 

13 = Range [1,8] + Range [9, 12] + Range [13,13]

= 40 + 22 + 1

= 63

 

So what we do is, we have these ranges pre computed. So when we get a range to calculate the sum, we first need to add those pre computed values.

 

How to pre-compute the values?

We calculate range in power of 2.

Hence the ranges will be 1, 2, 4, 8, 16, 32 …

 

In our example at the first level it can be computed as below

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

As you can see in the image above, we can infer below 3 points:

 

  1. We are calculating the range based on power of 2.
  2. While we are calculating the range values, there are gaps present
  3. We stopped at 2^3. Because, 2^4 is 16, that is outside of the range of our array.

 

So we computed our level 0. Next is level 1, we calculate the same from starting of the gap.

 

Before doing that, lets mark the index that we have calculated the values for.

Tree data structure tutorial 14. Fenwick trees and implementation

 

While filling the gap, we need to consider the gaps that are continuous.

 

From the image the index [3, 3] is having only 1 gap. Hence we calculate 2^0 = 1.

Tree data structure tutorial 14. Fenwick trees and implementation

Again the gap starts from the index [5], it is having continuous 3 gaps. Hence we calculate 2^0, 2^1. We don’t need to calculate 2^2 because it’s length is 4 and our gap is not that much long. Hence we leave it there.

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Now we look at the index [7, 7] as it is only 1 gap, we calculate only 2^0.

 

Next gap is from Index 9 to 14. Here again we calculate the value starting from 2 ^0.

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Now again we start from index 11. As it is only 1 gap we write as it is.

 

Next index is 13, the gap is 2. Hence we do 2^0, 2^1 sum range. It can be shown as below:

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Now that we have covered all the index, we can perform sum range query.

 

Now we want to know for the sum for range 13. We can write as

Sum (13) = range [1, 8] + range [9, 12] + range [13, 13]/

 

Now we can calculate easily as shown in image below:

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

We just need to add the highlighted value and we get our result “63”.

 

Now how does this actually help us? Let me make it easier for you.

 

The below image has the index represented as binary numbers

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Now the index of the ranges are:

 

1000 + 1100 + 1101

 

If you observe the index of 13 in binary is “1101”. When you flip the last digit “1” to “0”, you get the next index to be added i.e. “1100”. Now again you flip the last “1” to “0”, you get “1000” the index next number to add.

 

How to remove last set bit:

 

Get the last set bit by doing x & (-x)

Then remove the last set bit by x –x ( x &(-x))

 

In our example:

 

X  = 13 = 00001101

-X = -13 = 11110011

 

X & -X = 00000001

X – ( X & (-X)) = 00001100

 

Now we add an element at the given index.

Suppose we are given add 2 to index 5.

 

Starting from index 5 add 2. If we are not using Fenwick tree, we need to add 2 to all the ranges starting from index 5.

 

But as we have Fenwick tree constructed, we shall see how to do it.

 

For the index 5, first we add 2 to element at index 5

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Then we shall update all the ranges that are right side to index 5. As we have only one range [5, 6] we update that.

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

After the index 6, there is no continuous range related to 5. Hence we go one level up and update all the ranges.

 

Now we go to index 8 and update the value with 2.

 

Tree data structure tutorial 14. Fenwick trees and implementation

 

Hence we finished our updating values.

 

Now let’s look how we can achieve this by binary representation:

 

First we go to “5” i.e 0101, then we go to 0110, from there we go to 1000.

 

Basically we add the last set bit to know the next index to be updated.

 

Programmatically it can be achieved as below:

Get the last set bit by doing x & (-x)

Then add the last set bit by x + x ( x &(-x))

Implementation of Fenwick Tree in C

#include <stdio.h>

int FWtree[100] = {0};
int SIZE;

int get_sum(int i)
{
	int sum = FWtree[i];
	while(i)
	{
		i -= (i & (-i));
		sum += FWtree[i];
	}
	return sum;
}

void add(int i, int value)
{
	while(i < SIZE)
	{
		FWtree[i] += value;
		i += (i & (-i));
	}
}

void init_fw_tree(int my_array[], int start, int end)
{
	SIZE = end-start+2;
	for(int i = 1; i <= end-start+2; i++)
	{
		add(i, my_array[ start+i-1 ]);
	}
}

int main()
{
	int my_array[] = {1, 3, 2, 4, 5 ,8, 6, 5 ,0, 3, 4, 3, 2, 2};
	init_fw_tree(my_array, 0, 13);

	//get sum of all the numbers in the array
	printf("The sum of all the numbers in the array is = %d\n",get_sum(14));
	
	// update 5th index with value 8
	add(5,8);
	printf("The new sum after updating 5th index with value 8 is = %d\n",get_sum(14));

	return 0;
}

Output:

The sum of all the numbers in the array is = 48
The new sum after updating 5th index with value 8 is = 56

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

Leave a Reply Cancel Reply

You must be logged in to post a comment.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2023 ProDeveloperTutorial.com
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept”, you consent to the use of ALL the cookies.
Do not sell my personal information.
Cookie SettingsAccept
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT