Searching for an array prefix with a given amount

The task is as follows:
For a given value ‘x’ we have to quickly find the 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).

This task can be solved using binary search, computing the sum of the prefixes with the Segment Tree. However, this will lead to a O((logn)^2) solution.

Instead we can use the same idea as in the previous section, and find the position by descending the tree: by moving each time to the left or the right, depending on the sum of the left child. Thus finding the answer in O(logn) time.
this is taken from : https://cp-algorithms.com/data_structures/segment_tree.html
but I can’t understand the second paragraph the one which says about binary search. Can someone explain to me how to get the complexity of (log(n))^2

Prefix sums are monotonic, so you can binary search for your desired value. But, because it takes O(\log{n}) time to make a prefix sum query and you need O(\log{n}) queries for the binary search, the total time is O(\log^2{n}).

1 Like