Блог пользователя ZeyadKhattab

Segment Tree Problem
Автор ZeyadKhattab, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
← 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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← 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).

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +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".

→ Ответить