I have a set of time intervals In = (an, bn). I need to run lots of look ups where I'm given a time t and need to quickly return the intervals that contain t, e.g., those intervals such that an <= t <= bn.
What is a good data structure or algorithm for this?
If it matters, in my case the an and bn are integers.
This is basically a space partitioning question. You have a large space with containers and a specific point in that space, what containers does it touch? A lot of games have to solve this problem, so it wouldn't be a bad idea to start there. Look for articles on "broad phase collision detection".
The simplest way to do this is to divide your number space into a constant number of pieces. Each piece knows which sets intersect with it, something that you calculate whenever a new set is added. Now, rather than testing every single set when you have a point, you only need to check the sets contained within the piece that the point is in.
Another general and efficient algorithm used is Binary Space Partioning. This algorithm subdivides your space into two sides. Each side would know which sets intersect with it. You can recursively repeat this process to your desired precision (although it doesn't make sense to ever create a subdivision smaller than the range of your smallest set).
Your problem is only one dimensional, so it's a bit simpler than the space partitioning problems found in most games. You could have just a simple BST and in each leaf remember list of intervals to the left fromt the leaf.
if you had intervals A (0, 10) and B (5, 15), then the leaves of the tree would be (0 with empty list), (5 with A), (10 with A, B) and (15 with B).
What you are looking for is an Interval Tree (which is a type of Range Tree).
These have logarithmic lookup time like other tree structures (e.g., RB trees), so you should see comparable performance to using something like a Java TreeMap or an STL map.