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.