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)$

#### History

Revisions

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