# How can I implement a data structure which calculates the number of nested intervals in sub-linear time?

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.

• Maybe you are looking for an interval tree? Commented Feb 14, 2021 at 21:00
• 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. Commented Feb 14, 2021 at 21:57
• 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. Commented Feb 14, 2021 at 22:20
• 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.
– user114966
Commented Feb 15, 2021 at 17:12

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.