Are there existing algorithms / strategies to test if an integer value is within the limits of any one of a list of intervals, where each interval is denoted by a [min, max] pair?

The naive approach is very simple, but it has a test performance of O (intervals):

```
List intervals (min, max)
func testVal (val) {
foreach (interval (min, max) in intervals)
if (val> max) || (val <min) returns false
return true
}
```

In the problem that I face, the list is not updated frequently, but it is tested with a very high frequency.

Therefore, it is acceptable that updating the list is expensive, but the tests must be sublinear, ideally a constant time.

One option is to insert each value in the intervals in a hash table, but this requires a lot of memory and is not practical when the intervals are large. The use of memory should be proportional to the number of intervals, not the sum of the sizes of the intervals (it is probably fine to have a memory usage term log (n) included if this greatly helps the performance).

I started poking around with several tree-based options to improve this, but it seems a general enough problem that I suspect there is a pre-existing job that I should be referring to. Are there solutions to obtain sublinear tests (ideally constant time) in a list of intervals by preprocessing them in some other data structure?