Searching for an array prefix with a given amount

general
1

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 : Segment Tree - Algorithms for Competitive Programming
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

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}).

3 Likes
3

Q1 : - Is there any problem with solution like this one :-

first make a prefix sum array and binary search (find lower bound ) on all queries one by one.
Time complexity O(q*log \ n).

Q2 :- Time complexity of segment tree method is also O(q*log \ n) ?

4

you got the answer of your query ?

5 
template<typename T>int find_prefix_seg(vt & t,int v,int tl,int tr,int x){
	if(x>t[v]) return -1;
	if(tl==tr){
		return tl;
	}
	int tm=MID(tl,tr);
	if(t[2*v+1]>=x) return find_prefix_seg(t,v*2+1,tl,tm,x);
	return find_prefix_seg(t,v*2+2,tm+1,tr,x-t[v*2+1]);
}