Fast extraction of pairs overlapping an interval I am trying to find a fast algorithm to extract pairs that overlap with a specified interval.

Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 &lt;= x2, (you can imagine them two points on the x-axis or on a timeline to visualise the problem better). Provided 2 other values V1, and V2, also assuming V1 &lt;= V2, I want to extract the set of all pairs that satisfy at least one of the following criteria.


V1 &lt;= x1 &lt;= V2
V1 &lt;= x2 &lt;= V2
x1 &lt;= V1 &lt;= V2 &lt;= x2


So intuitively what I need to extract is all interval pairs that overlap with V1 and V2, either partially (criteria 1 and 2) or completely (criteria 3).

I wish to find a fast way to extract them (I know this depends on how large the interval between V1 and V2 is). The solution I came up with so far is organising the pairs in a balanced binary search tree sorted with just x1 and traversing it for items that are x1 &lt;= V2, and then checking the rest of the criteria as I am traversing the tree. I could also enhance it by adding another binary search tree sorted by x2 of the same pairs, and traversing similarly for pairs x2 >= V1, and maybe using this tree instead when the V1, V2 interval is biased towards the right of the midpoint of the whole range of values of the pairs.

Is there any better idea how I could achieve this? It seems I can only get O(n) complexity.
This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree.  Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.