Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
