ON THE COMPLEXITY OF MAINTAINING PARTIAL SUMS.

Let F equals left brace (r//i, s//i) vertical 0 less than equivalent to i less than n right brace be a file of n records, where r//i are d-dimensional vectors and s//i are elements of a commutative semigroup S. We are interested in the partial sum problem, in which queries of a particular form are to be answered. A space-time tradeoff t equals OMEGA (log n/log (m log n/n)) is established for storing a static two-dimensional file. It is also shown that for the one-dimensional problem, any dynamic algorithm must have a worst-case time OMEGA (n log n/log log n) in processing a sequence O(n) INSERT and QUERY instructions.