While learning about segment tree I came across this problem:-
The task is as follows: for a given value x we have to quickly find smallest index i such that the sum of the first i elements of the array a is greater or equal to x (assuming that the array a only contains non-negative values).
The solution mentions storing prefix sums in the segment trees.
I cannot figure out how to build up a segment tree of prefix sums. Also how is it different from the range sums?
No, we don't need to store the prefix sum. We just need to build the simple sum segment tree, it only differs in the way we query the segment tree. Let the required sum be K, idx represent the index of the segment tree and l and r be the array range it covers, then code will look like,
return query(2*idx+1, md+1, r, K-seg[2*idx]);
This is how I understood your code. Supposing the left child doesn't have the sum>=K so we go to right child and look for the K-left child sum. Now if the right child's sum is greater than K-left child sum the
lof the right child will be the answer. (since the sum of left child +this right child will end up greater than K)
This is how it is?
Yes, since we know answer do exist (see comments in the code), then if answer is not in the left child then answer will be in the segment covered by right child and hence we call the same function on the right child with sum of the left child removed
Thanks a lot!
Do you need to update the elements of the array?
If no, use binary search to find the first position.
Input 1: 5 6 1 2 3 4 5
Output 1: 2
Input 2: 5 7 1 2 3 4 5
Output 2: 3 ~~~~~
Otherwise, my solution would be to use a segment tree with range sums.
Thanks for the detailed implementation. Yes, I was looking for a O(log n) implementation using segment tree.