Coders Packet

Fenwick Tree implementation in C++

By UDDESHYA PANKAJ

Implementation of Fenwick Tree in C++ that finds a sum of a given range in a given array.

A Fenwick Tree also known as (Binary Index Tree) is a data structure that is used in Range Query Problems.

Queries include Range Sum,Range Maximum/Minimum in O(LogN) time complexity. Update data operations can also be achieved in O(LogN) time complexity.

Fenwick Tree is much simpler and easy to code and also takes less space as compared to Segment Tree which also has time complexity O(LogN).

 

Let us take an example for a clear understanding of how Fenwick Tree works:-

 

We have the array given as arr=[1,3,5,11,7,4,6,9] of size n=8.

Now we will construct the Fenwick Tree from the given array for finding the sum in a given range:-

fenwick tree

In Fenwick Tree we assume the starting index as 1.

From the above image, you can find how a Fenwick Tree is being constructed from the given array. We can see that the numbers written in (a,b) are the range sum from a to b inclusive and the value of the node is the sum from a to b.

Tree size= (n+1)

For Update:

We have to know to what index I will be updating next in fenwick tree so that can be known by formula 

suppose x is the index:

x + = (x & (-x))

For Query:

Suppose we want to find range sum, so in order to know which index we have to go next which comes in the given range we use the formula:

suppose x is the index:

x - = (x & (-x))

You can find the complete implementation of the Fenwick Tree in the code attached with this packet where you can  find out how to find a range sum and how to update a value(means construct the tree) in O(logN) time complexity.

 

Download project

Reviews Report

Submitted by UDDESHYA PANKAJ (uddeshya146)

Download packets of source code on Coders Packet