I wonder if there isn't a way to get O(1) query time by exploiting the nature of the keys and building a different data structure.

The keys here are dates. There aren't that many distinct dates in a year. By converting all dates to an offset from some given starting date, you can build an array indexible by date offset. Each element of this array, if present, holds an array of references to records that are "effective" on that date.