Fenwick tree Sum query

Question

This is the code for the sum query from Index 0 to Index X

Int query(int x){ 
Int sum=0;
for(; x>0; x -= x &(-x) )
   sum += BIT[x]; 
 Return sum; 
 }

I have two arrays BIT[] and a[]. I store the values from array a to BIT for queries. Now according to the loop, what we do is add value at index X and then change the index by removing the last set bit from it.

For eg if I call query(14) it will execute as follows :

Sum= BIT[14] + BIT[12]+ BIT[8]

It will stop after Index 8 as 8 is 1000 and after removing the last bit it becomes 0 and loop ends. So that means for index 14 I.e 1110 I access the array 3 times , I.e is the number of set bits. But I checked for long bits, it failed for eg 1000110111011101100set bits are 11 but the answer is 12 . So is there other way to tell how many times I access the array during the execution of sum query by seeing the binary value of a index I ?

I can't figure it out. I tried many cases , for some it is less by 1 , for some it is more by 1 and for some it is actually the answer.

Please help me out.

Don't forget to tag the language. In C for example, x &(-x) will depend on the complement scheme of the signed type. — Bathsheba
– Bathsheba, Commented Oct 10, 2016 at 12:30
@Bathsheba I don't require this code. All I want is to know the number of times I access BIT [] array for a given binary value of Index X. — Sam_Buck
– Sam_Buck, Commented Oct 10, 2016 at 13:45

Tahtisilma · Accepted Answer · 2016-10-15 12:20:08Z

1

Number of accesses is exactly number of ones in binary representation. Here is the short Python (Python just because I am lazy) script that would print something if it would not be the case any number smaller than 1000000

def count(x):
  ones = 0
  for ch in bin(x): 
    if ch =='1':
      ones = ones + 1
  return ones

access = 0;
for y in range(1000000):
  access = 0
  x = y
  while x > 0:
    x = x -(x & (-x))
    access = access + 1
  if count(y) != access:
    print "Wrong:"+str(y)

answered Oct 15, 2016 at 12:20

Tahtisilma

1291 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sam_Buck Over a year ago

I can't tell right now what is the right answer but there is specific condition for counting number of 1.

Tahtisilma Over a year ago

Maybe you think about updating the tree. For query it is number of "1". x&-x is the least significant bit. If you subtract it from x you get x with one less "1".

Collectives™ on Stack Overflow

Fenwick tree Sum query

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related