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.
- Code for Red-black trees and interval trees from MIT
- There is a C++ implementation in the CGAL Library.
- Here’s a C# Implementation