You are not logged in. Please login at to post your questions!


Doubt in range update and point query in Binary Indexed Tree

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].


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

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

sum = 0
for(; b > 0; b -= b&(-b)) sum += ft[b] return sum

PS : the above code is taken from :

asked 21 Apr '14, 19:00

herman's gravatar image

accept rate: 0%

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


answered 21 Apr '14, 19:11

damn_me's gravatar image

accept rate: 24%

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

(21 Apr '14, 19:21) herman3★

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.

(21 Apr '14, 19:43) damn_me3★

As mentioned here : 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?

(21 Apr '14, 19:50) herman3★

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.

(21 Apr '14, 21:37) damn_me3★

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

(21 Apr '14, 23:40) herman3★

answered 21 Apr '14, 23:42

herman's gravatar image

accept rate: 0%

thanks @ herman for giving the link to the correct comment


answered 30 Sep '15, 12:41

muthukkaruppan's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 21 Apr '14, 19:00

question was seen: 4,390 times

last updated: 30 Sep '15, 12:41