Lower Bounds on the Complexity of Some Optimal Data Structures

A technique is presented for deriving lower bounds on the complexity of optimal data structures which permit insertions and deletions of records, and queries of the form \[ {\text{Query (Region)}};\quad {\text{Return}}\quad \sum_{\begin{subarray}{l} {\text{key}}(r) \\ \in {\text{Region}} \end{subarray}} {{\text{value }}(r)} \quad ({\text{Region}} \in \Gamma ), \] where value$(r)$ (the value associated with a record r) lies in a commutative semi-group S, and $\Gamma $ denotes a set of regions of the space of possible keys. This technique is illustrated with several examples.