Data structure for set of intervals - query for all intervals contains given point

We're given a set of $n$ intervals $[a_i, b_i]$, $i=1...n$. I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$.

My proposition is using two-dimensional interval (sometimes name is segment) tree. Each query will take $O(\log^2 n + k)$ time, where $k$ is number of interval such that contains point $x$.

Is this correct? Is there a better solution?

1 Answer

There are many algorithms for this kind of problem. See, e.g., segment trees and interval trees. The kind of query you mention is known as a "stabbing query".

A segment tree takes $O(n \lg n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time, where $n$ is the number of intervals and $k$ is the number of intervals that contain $x$. An interval tree takes $O(n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time. Segment trees are static: they can't be easily modified after they're created. Interval trees are dynamic: you can insert or delete an interval in $O(\lg n)$ time.

Other data structures exist as well. There are also generalizations to higher dimensions, though the running time gets worse in higher dimensions.

• Ok, pay your attention that these intervala are given, it means that it is not possible to delete/add intervals. Could you give an intuition about how to do stabbing query ? – user40545 Jan 6 '16 at 21:36
• @user40545, yup, I saw that. Thank you for highlighting that. I was just giving additional information, in case it was helpful to you or anyone else who stumbles across this question. To learn how to do a stabbing query, I suggest reading about those data structures in Wikipedia and other standard resources -- it should all be described. – D.W. Jan 6 '16 at 21:38
• I have one question: What about situation when instead of poinf $x$ the query is about interval $[a, b]$ ? – user40545 Jan 6 '16 at 21:42
• @user40545, please read the references before asking. For instance, on the Wikipedia page I pointed you to one already finds en.wikipedia.org/wiki/Interval_tree#With_an_Interval. Please do more research and self-study before asking follow-up questions; then if you have a question that isn't answered by standard resources and you can't figure out on your own, ask a new question rather than posting a comment here. Comments are not intended for follow-up questions (this isn't a discussion forum). Thank you! – D.W. Jan 6 '16 at 23:20