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