Searching for an array prefix with a given amount. (using segment trees)

Revision en1, by weakestOsuPlayer_244, 2020-04-26 06:31:22

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?

Tags segement tree, prefix sum


  Rev. Lang. By When Δ Comment
en1 English weakestOsuPlayer_244 2020-04-26 06:31:22 626 Initial revision (published)