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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
I guess I misunderstood the problem. Apologies. Please refer the comment by RedNextCentury.
I think you misunderstood the question, he's asking for the minimum index not value.
Ah right, Sorry. I'll edit the answer.
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.
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?
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).
I get it now, thank you !
This method is well known as "fractional cascading". You can refer to it here: http://e-maxx.ru/algo/segment_tree ZeyadKhattab
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".