# 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?

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.
• 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