DIMACS TR: 93-91

Balancing Updates vs Queries for the Partial Sum Problem

Authors: Haripriyan Hampapuram and Michael L. Fredman


Partial sums problem is one of the least complicated example of non-trivial range query problem. The problem concerns with design of a data structure for maintaining an array A, with the following two operations. The operation update(j,x), adds x to A[j], and the operation sum(j) returns the value of A[1]+...+A[j]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semi-group model of computation. We introduce a new data structure called the bi-weighted tree, and show how this leads to balancing update vs. sum operations.

Paper only.
DIMACS Home Page