CODEWITHSUNDEEP
stringbinarylogicbinary-indexed-tree
Sam_Buck
Sam_Buck

Reputation: 25

Fenwick tree Sum query

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.

Upvotes: 0

Views: 333

Answers (1)

Tahtisilma
Tahtisilma

Reputation: 129

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)

Upvotes: 1

Related Questions