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?

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 ? Jan 6, 2016 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, 2016 at 21:38
• I have one question: What about situation when instead of poinf $x$ the query is about interval $[a, b]$ ? Jan 6, 2016 at 21:42