ZeyadKhattab's blog

Segment Tree Problem
By ZeyadKhattab, history, 6 years ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I guess I misunderstood the problem. Apologies. Please refer the comment by RedNextCentury.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think you misunderstood the question, he's asking for the minimum index not value.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like 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).

      → Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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".

→ Reply