You are not logged in. Please login at www.codechef.com 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].

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

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

asked 21 Apr '14, 19:00

herman's gravatar image

3★herman
514512
accept rate: 0%


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

http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

link

answered 21 Apr '14, 19:11

damn_me's gravatar image

3★damn_me
2.6k21336
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 : 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?

(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★
link

answered 21 Apr '14, 23:42

herman's gravatar image

3★herman
514512
accept rate: 0%

thanks @ herman for giving the link to the correct comment

link

answered 30 Sep '15, 12:41

muthukkaruppan's gravatar image

2★muthukkaruppan
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×326
×249
×146

question asked: 21 Apr '14, 19:00

question was seen: 4,371 times

last updated: 30 Sep '15, 12:41