I’m looking for a data structure that would help me find the smallest interval (the (low, high) pair) that encloses a given point. Intervals may nest properly. For example:
Looking for point 3 in (2,7), (2,3), (4,5), (8,12), (9,10) should yield (2,3).
During the construction of the data structure, intervals are added in no particular order and, specifically, not according to their nesting. Is there a good way to map this problem to a search tree data structure?
Segment tree should do the job. In nodes of a segment tree you keep the length of the shortest interval that covers this node, as well as the reference to the interval itself. When processing a query for a given point, you simply return the interval referenced by the node of that point.