Best data structure to efficiently allow pull of all ranges (min,max) such that value >= min and value <= max?

Imagine that I have a set of min values and max values. I want a data structure that, given an outside value, will most efficiently give me the (min,max) pairs for which value >开发者_开发技巧= min, value <= max.

If you know the ranges are non-overlapping, I imagine you could just do a balanced binary search tree on min, and the first node that has a (min,max) that is satisfied has to be the only one. But if the ranges can overlap, is there a data structure that can let you do this efficiently?

---

The problem you are describing is also known as "stabbing query". It is well described in graphics-programming text-books, where this is a very relevant problem.

Also, the wikipedia page on segment trees might help. Those trees are the data structure that is commonly used to solve this problem.

---

I think the answer might actually be this http://en.wikipedia.org/wiki/Interval_tree. Given a point or a set of points, it allows you to efficiently pull satisfying intervals. The only caveat, of course, being that the construction of the initial data structure is not efficient, but that's also inevitable in any indexing etc.

---

One possible approach is to put the (min,max) in an array, and sort by mind Then use binary search to find the area in the array where the mins meet the criteria then search.

---

The query can be solved with a Range Tree: a binary tree of binary trees.

The outer tree is a search tree on the values x of the pairs (x, y). The pairs (x, y) are stored in the leaf nodes. Each node V of the outer tree contains a pointer to a y-indexed search tree Y, containing all the pairs of the subtree of V.

To solve a range query ([Value, infinity) = RangeX, RangeY), search down the outer search tree for the leftmost x_min satisfying Value <= x_min. Let V be a node on the path to x_min. If the search goes to the left, then the search tree Y of the right subtree of V contains pairs that are all in RangeX. Add all pairs of Y that are in RangeY to the result.