You could have a table with 3 columns: XCoord, YCoord, and Value. The PK would be on XCoord and YCoord which would give lookups as fast as possible. Also, since it is the PK there would only be one read: no need to look up the index and then go read the data page: the index is the data page.
I'm not sure how you calculate an O number for SQL lookups, but if you keep the index stats up to date and defrag it regularly, this is as close to O(1) as you're going to get.