1
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – user40545 Jan 6 '16 at 21:36
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Jan 6 '16 at 21:38
  • $\begingroup$ I have one question: What about situation when instead of poinf $x$ the query is about interval $[a, b]$ ? $\endgroup$ – user40545 Jan 6 '16 at 21:42
  • $\begingroup$ @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! $\endgroup$ – D.W. Jan 6 '16 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.