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

Правка en1, от 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).

Link-https://cp-algorithms.com/data_structures/segment_tree.html

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?

Теги segement tree, prefix sum

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский weakestOsuPlayer_244 2020-04-26 06:31:22 626 Initial revision (published)