Doubt related to binary indexed trees

general
, , ,
1

hello everyone,I have a doubt regarding BIT.I came across this tutorial which is pretty good but i have doubt that after updating the range why query() function starts reporting value at particular index rather than cumulative sum from 1 to b(say) for which it is defined before.Second doubt In this question it was defined that the heaps have C no. of gravels from the beginning. I want to know that is this way to initialise empty tree with C gravels correct??my solution have a look and please let me know link text…Thanks

2

anybody please???

3

Your answer lies in the comments there itself, read the questions on the same tutorial. Any further help, can be asked here or there also. In that question, C gravels means initially the array of n elements have value c i.e. each a[i]=c. So, you can assume here that the array initially has all zero elements and then in query just add c to the value returned by your query function. Alternative can be, you may allocate an array of n elements and assign each a[i]= c and construct BIT corresponding to this array. The query function will then be used in the way you have used. Former is simply I think, you may see my code for the same question.

If you understood, can you please explain the point query part of your doubt first as mentioned in that comment on blog. Although I got it, but unable to visualize it in a good manner. It’ll be good if you can explain it in comments or as an answer to this post only.

4

thanks i got it…can you see my code . My intialization with with c gravels :slight_smile:

5

See the edit above…

6

which one Range update and point query??if yes,this is what i have understood so far(i may be wrong because i am still learning so please please do confirm twice ) .I think you are asking why update(b+1,-v)??See on calling of update function update(p,v) it will add v to all subarray(i think its called subarray) for indices >=p…So to reverse the effect and to keep it to range (a,b) we substract v from all subarrays for indices >b…This change the semantic behavior and query starts reporting value at certain index.