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 v v x j j ← + , and the query operation retrieve(i,j) returns the partial sum i j v +K+ v . 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.

Keywords: zero-one matrices, lower bounds, matrix equations

ACM Classification Keywords: F.2.1 Numerical Algorithms and Problems

Link:

MATRICIAL MODEL FOR THE STUDY OF LOWER BOUNDS

Jose Joaquin Erviti, Adriana Toni

http://www.foibg.com/ijita/vol13/ijita13-1-p09.pdf