Query time versus redundancy trade-offs for range queries (Q800105)

Let S be a commutative semi-group. Let \(A(1),A(2),...,A(n)\) be an array which stores values in S. The problem is to find data structures for representing A(i) such that the range query problem \[ Return\sum^{k}_{i=j}A(i)\quad (1\leq j\leq k\leq n) \] can be efficiently implemented. The trade-offs between the degree of redundancy \({\mathcal P}\) of A(i) and the query time t in a large class of possible data structures is investigated in this paper. These concepts are formally defined. The authors then show that \({\mathcal P}+t=\Omega (\log n)\) for any data structure in the class. This shows that it is near optimal to consider the natural data structure of a minimal height binary tree with n leaves where in the ith node is stored not only the value A(i) but also the sum of the values A(j) stored in the leaves of the subtree beneath that node; the degree of redundancy here is \(\log_ 2 n\). The authors also show that the above result is best possible.