 # A small doubt in Binary indexed tree

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

@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

https://codeforces.com/blog/entry/619

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

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??

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

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

3 Likes

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

//