Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval
Here's my thought process on this problem:


If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order.


Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes.

For a given point and a given interval, you can determine whether the point is "outside to the left", "inside", or "outside to the right" in $O(1)$.


This assumption only works as long as you have a fixed word length, but that's generally true for all practical purposes.
Let's change the terms: "outside to the left" is "less than", "inside" is "equal to", and "outside to the right" is "greater than".

Now you can use standard binary search!


Since each comparison is $O(1)$, the total time is $O(\log n)$.



And voilà, each check takes only logarithmic time! Setting up the list in the first place takes $O(n \log n)$, and adding a new interval to the list later takes $O(n)$ in the worst case.