3
$\begingroup$

Is there a data structure which can maintain a list of intervals and the following operations?

insert(l, r): Inserts an interval [l, r] into the list
query(l, r): Return the number of intervals in the list which are completely nested in [l, r]

I need the data structure to handle inserting and querying without brute force (which would take linear time).

I saw this algorithm for counting the number of nested intervals for each interval here: https://stackoverflow.com/questions/12946497/sub-on2-algorithm-for-counting-nested-intervals but it appears to only calculate the answer for a static array of intervals.

$\endgroup$
4
  • $\begingroup$ Maybe you are looking for an interval tree? $\endgroup$
    – STanja
    Commented Feb 14, 2021 at 21:00
  • $\begingroup$ An interval tree can only answer 'how many intervals overlap with a given interval', but I'm looking for the number of intervals which are entirely contained within an interval. $\endgroup$
    – pblpbl
    Commented Feb 14, 2021 at 21:57
  • $\begingroup$ You could modify the query algorithm by filtering all the overlapping intervals which are completely contained in the query-interval, but perhaps there's a better option. $\endgroup$
    – STanja
    Commented Feb 14, 2021 at 22:20
  • 1
    $\begingroup$ Treat your intervals as 2D points. Essentially, you need to find the number of points $(x,y)$ such that $x \ge l$ and $y \le r$. This can be solved using e.g. 2D segment tree or QuadTrees. $\endgroup$
    – user114966
    Commented Feb 15, 2021 at 17:12

1 Answer 1

2
$\begingroup$

Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals.

This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when rebalancing the outer tree you have to rebuild the inner trees, but I think it can be made amortized polylog(n) if you rebalance sufficiently rarely, using a scapegoat tree for example.

If you know that the endpoints will belong to a set of size $k$, and you don't mind factors of $\log k$ in the insertion and lookup times, then you could use a radix tree for the outer tree and avoid the rebalancing logic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.