The inherent complexity of dynamic data structures which accommodate range queries
Michael L. Fredman · 1980
A formal framework is presented in which to explore the complexity issues of data structures which accommodate various types of range queries. Within this framework, a systematic and reasonably tractable method for assessing inherent complexity is developed. Included among the interesting results are the following: the fact that non-linear lower bounds are readily accessible, and the existence of a complexity gap between linear time and n log n time.