A small doubt in Binary indexed tree

general
1

Given an array, 1-D, how e have to kake the corresponding BIT for that?
ex. if the array is 10 8 5 9 1
what will the BIT for this?

1 Like
2

@rajatgupta93 You can find everything you need to know about BIT (or Fenwick tree) in this answer. This is the best BIT reference I have seen on the internet.

Thanks & Regards

CrucifiX

3

If you want to know about BIT and have no knowledge about it . I strongly recommend reading the above mentioned blog post . Once you get the basic understanding then it will be easy for you to understand other tutorials

4

@rajatgupta93 tree for ur example will be 10 18 5 32 1 suppose array name is A
if index is 1 then tree[1]=10;
index is 2 then tree[2]=A[1]+A[2]=18
index is 3 then tree[3]=A[3]=5
index is 4 then tree[4]=A[1]+A[2]+A[3]+A[4]=32
index is 5 then tree[5]=A[5]=5;

3 Likes
5

@rajatgupta93,if r=0 then idx-2^r+1=`idx
Don’t do this type of silly mistake

6

I read the above blog and even the topcoder one also…
My doubt goes like while making the bit[],
idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx - 2^r + 1) to index idx , then how is this true if idx is 3??

7

Because if idx is 3, r is 0 then idx - 2^r +1 is 4, so, bit[3] will have summation of frequencies from 4 to 3?? I know m getting something wrong… but please i would like to clarify!!