# Algorithm for answering queries of the type "largest interval contained in the given interval"

I have been wondering over the following problem:

Given a set $$S$$ of intervals on the number line. We can do two operations on them:

1. Add a new interval $$[l_i,r_i]$$ to $$S$$
2. Given an interval $$[l_j, r_j]$$, which is possibly not in $$S$$, find the longest interval from $$S$$ which is contained entirely in $$[l_j, r_j]$$

If I didn't have operation $$1$$ I have found a solution using a persistent segment tree.

For the full version, there is the trivial solution which runs in $$O(QN)$$ ($$Q$$ - number of queries, $$N$$ - total number of intervals added). I also found that using interval tree, I can directly find which intervals intersect the query interval and then I can check them manually. However, is there an even better solution? Maybe $$O(Q\log N)$$ or $$O(Q\log^2N)$$?

• @thefunkyjunky Please add a reference to the original problem. Commented Jul 4, 2019 at 14:35
• @Apass.Jack sorry, I'll add explanations for Q and N. There is no original problem(you can say I made it up), that's why I am asking if there is a better solution. Commented Jul 4, 2019 at 16:18
• I'm a bit confused about your notation. Your first bound is $O(QN)$, which makes me think that what you're measuring includes the time to process all queries. Your second bounds, however, don't include $Q$ at all. But if you're processing all queries, the answer must be at least $\Omega(Q)$, since you have to read every query. Commented Jul 7, 2019 at 22:00
• @jbapple, fixed. Commented Jul 7, 2019 at 22:27
• Can you describe your solution using a persistent segment tree? Commented Jul 7, 2019 at 22:32