Institute of Information Theories and Applications FOI ITHEA
Abstract:
Let V be an array. The range query problem concerns the design of data structures for implementing
the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation
retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an
algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well
a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower
bound is near optimal – in terms of asymptotic complexity.