You can think of a Binary Indexed Tree as supporting two operations.

- Get the sum of a[1] + a[2] + … + 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[1] + a[2] + … 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[1] + a[2] + … + 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[1] + a[2] + … + 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[1] + a[2] + … + 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[1] + tree[2] + … + tree[k].

I’m a bit drunk from last night so excuse any spelling errors.