You can think of a Binary Indexed Tree as supporting two operations.
- Get the sum of a + a + … + a[n].
- Update the element a[i] (this of course updates the entire array from i + 1 … n accordingly)
Now to extend this to the above task. You want a + a + … a[k] to be the number of stones on the kth pile, for this you should simply increase a[k] by the number of stones on the kth pile, and
decrease a[k + 1] by the same number.
Now for range updating. Suppose you want to increase all the stones from piles i … j by some given number x. What you do is update a[i] by x (ie call update(i, +x)), and this increases every element from i … n (because from some number k > i, a[k] is defined as a + a + … + a[i] + a[i + 1] + … + a[k]). So now you have to decrease everything in range from j + 1 … n by -x, that is call update(j + 1, -x), this results in you only increasing elements in range from i … j by x.
We defined a + a + … + a[k] to be the number of stones on the kth pile, so for querying just query the cumulative sum on the kth pile, ie output query(k).
To recap the algorithm is as follows :
- Read the array and for every x[i] from the call update(i, x[i]) and update(i + 1, -x[i]).
- Read queries and for every update query call update(i, value) and update(j + 1, -value).
- For every query that asks you to ouput number of stones on the kth pile pile output cumulative sum
a + a + … + a[k], which we defined to be the number of stones on the kth pile, ie call query(k).
Here a is binary indexed tree, and x is the initial array of stone piles.
PS Your algorithm just isn’t correct what you are simply outputting is a[k] (or tree[k] in your case), which is nothing. You don’t need a function read() for it you can just simply write cout << tree[k] << endl; you’re going to get the same result. You need to output tree + tree + … + tree[k].
I’m a bit drunk from last night so excuse any spelling errors.