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

Question

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.

Answer 1

It is a very strong assumption that the time it takes to preprocess is not a concern.

Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.

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 } p<a_1,\\ 1&\text{ if } p= a_1,\\ c_{i}&\text{ if } a_i<p\lt a_{i+1}\text{ or } p=a_i\text{ and } c_i>c_{i-1},\\ c_{i}+1&\text{ if } p=a_i\text{ and } c_i<c_{i-1},\\ 1&\text{ if } p=a_{2n},\\ 0&\text{ if } p>a_{2n},\\ \end{cases}$$ In other words, we can get the answer in $O(\log n)$ time once $A$ and $C$ are known.