Doubt in range update and point query in Binary Indexed Tree

bit
doubt
fenwick

#1

Hello all.

Can anyone explain why this code(for range update and point query) works? When i read BIT from topcoder tutorial they said that query(x) returns array[1]+array[2]…+array[x] but here query(x) returns only array[x].

CODE:

update(p, v):
for (; p <= N; p += p&(-p)) ft[p] += v

update(a, b, v):
update(a, v)
update(b + 1, -v)

query(b):
sum = 0
for(; b > 0; b -= b&(-b)) sum += ft**
return sum

PS : the above code is taken from : http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/


#2

Refer to this, read properly and u’ll come to know the whole processing which goes on in BIT.


#3

Finally the following comment solved my doubt : http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/#comment-2499


#4

thanks @ herman for giving the link to the correct comment


#5

Thanx for the link but actually i was asking only about the part that : “why query(x) returns value of element at index x”.


#6

Are you not getting this line for(; b > 0; b -= b&(-b)) sum += ft** return sum ? If yes, then inside the for loop, we are traversing the nodes in the tree we make for storing the sum.


#7

As mentioned here : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees in “Read cumulative frequency” section read(int indx) or query(indx) returns array[1]+array[2]+…array[indx] but in the code (the one in question) query(indx) returns array[indx]. So what is the reason that inspite of same implementations(for update and query), here(code above) we get value at that index only but in the topcoder article we get cumulative sum by executing query function?


#8

I suppose you are getting confused unnecessarily or may be I. query(indx) is returning the sum[1…b] which if u’ll form the cumulative frequency array gets stored at array[indx] but when u apply the whole BIT procedure we don’t need array[indx] but sum of specific values whose indices are calculated in the for loop.


#9

@damn_me thanks for answering :slight_smile:
I think may be my question wasn’t clear.But anyways my doubt is solved.