The spanning bound as a measure of range query complexity

The subject matter of this paper concerns the complexity of data structures which permit insertions and deletions of records, and range queries of the form Query (Region); Return Σ_{key(r) ? region} value(r) (Region ? Γ), where value(r) (the value associated with a record r) lies in a commutative semigroup S, and Γ denotes a set of regions of the space of possible keys. A combinatorially defined quantity called the spanning bound is defined and is shown to provide a lower bound for the inherent worst case complexity of a sequence of n interminxed insertions, deletions, and range queries. Moreover, the strength of the spanning bound is demonstrated by proving the existence of data structures which come close to achieving it.