Fenvick Tree

Fenwick Tree aka Binary Indexed Tree (BIT) is a data structure which can handle Range Sum Queries very easily. The advantage it has over the segment trees, which is another data structure which is used for range queries, is that it has a less complicated implementation than the segment trees.The data structure itself is implemented on array

The idea is that each of the element in fenvick tree is responsible for storing the sum of fixed set of elements in the original array.  

 If m is th largest integer s.t. 2^m divides i then  

  FT_i = A_i-1+A_i-2+...+A_i-2^m

 

For eg as illustrated in the figure 

• FT₆ = A₅+A₄  (since 6 is divisible by 2 it will store sum of 2 elements)
• FT₁₂ = A₁₁+A₁₀+A₉+A₈  (since 12 is divisible by 4)

Lets define some terms for the Fenvick Tree

• b_i : The largest power of 2 which divides i.
• Predecessor(i): i-b 
• Intitutively speaking it is the index for the range which is just previous to range for i. For eg Predecessor₆ = 4 (as illustrated in the figure)

• Parent(i) : i+b
• Intutively it is the index whose sum range encompasses the sum range of i. For eg Parent₆ = 8 (as illustrated in the figure)

Inorder to calculate above 2 quaintities we need to find b. Now if we see the binary representation of i, then number of 0's at the end of representation give us the largest power of 2 that divides i. 

For eg take i = 6

⇒  i = 6₁₀

⇒ i = 110₂

Since their is only one zero at the end so b = 2  = 2

Now the question is how to get this number efficiently

Let's consider i = 1001000₂

⇒    i = 1001000₂

⇒   ~i = 0110111₂

⇒ ~i+1 = 0111000₂

So if we calculate i&(~i+1) (& is the bit-wise and)

⇒  i&(~i+1) = 0001000₂

We can see that i&(~i+1) = b_i

Also (~i+1) is the 2's complement of i so (~i+1) = -i

So,

b_i = i&-i

How to use it?

The Fenvick Tree handles 2 types of queries:

• Update Query
• Range Sum Query

Update Query

Lets say we want to change the value of A₁

As highlighted in the figure above we need to change the values of elements in FT which have A₁ included i.e. FT₂,FT₄ and FT₈, i.e. all the successive parents.

Complexity Θ(log(max_index))

Range Query

Lets say we want to find sum of first 11 elements.

 

So by seeing the figure above we can say 

A₀+A₁+..+A₁₀ = FT₁₁+FT₁₀+FT₈

That is sum of FT11 and then the successive predecessors.

Similarly we can find any prefix sum(sum of first i elements) via following

Complexity Θ(log(max_index))

Now the question is how to find A_i+..+A_j where i > 0.

The fenvick treeis not able to handle these types of queries directly. But since we are performing addition we can say

A_i+..+A_j = prefix_sum(j)-prefix_sum(i-1)

Hence we can also find sum for general range also.

If not for addition we would not be able to handle general range queries in this data structure. This is one of disadvatages it has against segment as we cannot handle Max or Min Range Queries in this. For that we require that we use more than one Fenvick Tree.

So hope I was able explain logic and usage of Fenvick Tree in well understandable manner. In case of any queries,suggestions or any mistakes please comment below.