Answering queries of the type "longest interval contained in the given interval"

Revision en1, by AnotherRound, 2019-07-09 16:26:47

I recently asked a question on cs.stackexchange, but since I got no answers there, I figured I should ask here too :)

The problem is the following: We are given a set of intervals (if you want, make it empty in the beginning). Then we have $$$Q$$$ queries, which are of one of the following types:

  1. Add a new interval to the set
  2. For a given query interval $$$[l_i, r_i]$$$, find the length of the longest interval from the set which is contained entirely inside $$$[l_i, r_i]$$$.

As mentioned in the linked question, if we didn't have query type 1, we can do a persistent segment tree and handle the queries. I have also been thinking we can do SQRT decomposition and answer in $$$O(Q\sqrt Q)$$$. Is there a better algorithm? I would like to be able to do this in $$$O(Q \log Q)$$$ or $$$O(Q \log^2 Q)$$$

Tags intervals, queries


  Rev. Lang. By When Δ Comment
en1 English AnotherRound 2019-07-09 16:26:47 1004 Initial revision (published)