DIMACS TR: 93-91
Balancing Updates vs Queries for the Partial Sum Problem
Authors: Haripriyan Hampapuram and Michael L. Fredman
ABSTRACT
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