## 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