By ZeyadKhattab, history, 13 months ago, ,

How can we solve the following problem efficiently (I am mainly looking for a Segment Tree solution) ? Given an array of integers A of size N , and Q queries of the form L,R,X we need to find the minimum index i such that L<=i<=R and A[i]>=X 1<=L<=R<=N and |X|<=10^9 1<=N<=10^5 1<=Q<=10^5 |A[i]|<=10^9 for 1<=i<=N

• +7

 » 13 months ago, # | ← Rev. 2 →   +8 I guess I misunderstood the problem. Apologies. Please refer the comment by RedNextCentury.
•  » » 13 months ago, # ^ |   +5 I think you misunderstood the question, he's asking for the minimum index not value.
•  » » » 13 months ago, # ^ |   +8 Ah right, Sorry. I'll edit the answer.
 » 13 months ago, # | ← Rev. 3 →   +20 The problem is identical to finding the minimum index i such that max(A[L]...A[i]) ≥ X O(log2(n)):Binary search to find the answer, the check is a range max query.O(log(n)):Let the segment tree store the maximum element in range. For the query, start from the root of the segment tree, you have two cases:1) The range of this node is not completely covered by the query range:Query the left child, if it returns an answer, immediately return that. Otherwise, query the right child.2) The range of this node is completely covered by the query range:If the maximum element in the left child's range is greater than X query the left child and return that. Otherwise if the maximum element in the right child's range is greater than X, query the right child.
•  » » 13 months ago, # ^ |   +8 Concerning the O(log(n)) approach, i thought about it, but i was not sure about its complexity. Can you help in proving this complexity or provide an intuition for it?
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +5 In the first case (The range of this node is not completely covered by the query range), we query both children (just like normal segment tree).In the second case (The range of this node is completely covered by the query range), we are only querying one child (at most) so this is O(log(n)) (depth of tree).The second case will only occur at one node because if a child returns a solution we don't query the second child.I forgot to write that in the second case you only query the right child if the maximum element in it's range is also greater than X (edited the first comment to clarify that).
•  » » » » 13 months ago, # ^ |   +8 I get it now, thank you !
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   +13 This method is well known as "fractional cascading". You can refer to it here: http://e-maxx.ru/algo/segment_tree zeyad49
 » 13 months ago, # |   +18 Moreover, a simpler solution would be constructing a sparse table so you can answer range-max queries in constant time. Rest is a simple binary search.But if you are looking for only segment tree solution, the above comment is well written. It is also called "parallel binary search".