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?

**@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[3] 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[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;