I imagine an indexed RDBMS could do this in a fraction of a second? I get that this is more of an academic exercise, but it also kind of explains why you might prefer one solution over another for a given task.
Maybe it could answer the question for an already indexed data set, but it probably couldn't INSERT 1 billion rows and then answer the question within that time. The ingestion is part of the challenge.