# How to find the number of intervals containing a point when given a static set of intervals?

I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.

I'm given a set of intervals $$\{s_1,s_2,...,s_n\}$$ where each interval has a starting point $$b_i$$ and an ending point $$r_i$$. Also, the set is not changing meaning no new intervals are inserted or removed, and no end/start points are identical.

I want to be able to return the number of intervals in $$O(\log(n))$$ time. I am aware of an interval tree however I actually don't have to worry about insertions and deletions so there might be something simpler.

Also, say I use an AVL tree where I use the start points as keys, and in each node I hold:

• start - the start point of the interval
• end - the end point of the interval
• max - the max end point of an interval that is contained in the tree initiated at this node

And I search like so:

Given a point $$p$$, I start at the root and go down based on the max value compared to the point. If $$p$$ is greater than the max of the node, I'm currently at I consider it's right sub-tree. If $$p$$ is smaller than max, I consider the right sub-tree until I hit null or I find an interval that contains the point(based on start and end points).

This algorithm can return an interval that contains $$p$$ in $$O(\log(n))$$ time, but what if I wanna return the number of all intervals that contain it?

I understand it can be done in $$O(\log(n)+k)$$ time, where $$k$$ is the number of intervals containing the point but can't see really how.

• "This algorithm can return an interval that contains $p$ in $O(\log(n))$ time". You do not include the time it takes to build an AVL tree, do you? Do you mean the algorithm should preprocess all $[b_i,r_i]$, whose time-complexity should not be included? May 16 '19 at 12:49
• The time it takes to preprocess is not included, just retrieving the intervals that contain that point. May 16 '19 at 13:45
• Are you aware of the segment tree? May 18 '19 at 7:35

Sort all $$b_i$$ and $$r_i$$ into an increasing sequence $$A=(a_1, \cdots, a_{2n})$$. Let $$c_1=1$$. For $$i$$ from 2 to $$2n-1$$, let $$c_{i}=\begin{cases} c_{i-1}+1&\text{ if } a_{i}\text{ is a starting point of a given interval,}\\ c_{i-1}-1&\text{ if } a_{i}\text{ is an ending point of a given interval.} \end{cases}$$ $$c_i$$ is the number of the given intervals that contain the open interval $$(a_i, a_{i+1})$$ for $$1\le i\le 2n-1$$. Let $$C$$ be the sequence $$(c_1, \cdots, c_{2n-1})$$. The combination of $$A$$ and $$C$$ is what we wanted from preprocessing.
Given any number $$p$$, if $$p \gt a_1$$ and $$p\lt a_{2n}$$, we can find the largest index $$i$$ such that $$p\ge a_{i}$$ by binary search in $$O(\log n)$$ time. Then the number of given intervals that contain $$p$$ is given by $$\begin{cases} 0&\text{ if } pc_{i-1},\\ c_{i}+1&\text{ if } p=a_i\text{ and } c_ia_{2n},\\ \end{cases}$$ In other words, we can get the answer in $$O(\log n)$$ time once $$A$$ and $$C$$ are known.