Efficient membership check in multiple ranges Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l_n$, upper bound $u_n$).

The program receives a number $x$; it must return all ranges in $S$ that enclose $x$.

An example in practical terms: in timeseries data, you have a set of $n$ independent events that occur over ranges of times. Given a point in time, you want to find the events that coincided with that point.

The naîve $O(n)$ solution:

out ← {}
for r in S:
  if (r.l ≤ x and r.u ≥ x):
    out.add(r)
return out


Is there a strategy for sublinear membership checking (in terms of $n$)?
An interval tree can retrieve intervals containing a specified point in $O(\log n)$. If the set of intervals is fixed, it is very easy to implement.