×

# Doubt in range update and point query in Binary Indexed Tree

 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[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 3★herman 51●4●5●12 accept rate: 0%

 1 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 answered 21 Apr '14, 19:11 3★damn_me 2.6k●2●13●36 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★
 1 Finally the following comment solved my doubt : http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/#comment-2499 answered 21 Apr '14, 23:42 3★herman 51●4●5●12 accept rate: 0%
 0 thanks @ herman for giving the link to the correct comment answered 30 Sep '15, 12:41 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×371
×311
×146

question asked: 21 Apr '14, 19:00

question was seen: 4,523 times

last updated: 30 Sep '15, 12:41