Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP
Newsgroups: ut.theory
Subject: THEORY NET: On the complexity of maintaining partial sums
Message-ID: <5696@utcsri.UUCP>
Date: Sun, 22-Nov-87 20:49:17 EST
Article-I.D.: utcsri.5696
Posted: Sun Nov 22 20:49:17 1987
Date-Received: Wed, 25-Nov-87 02:41:01 EST
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 18

Date:         18 Nov 1987 13:11:39-EST (Wednesday)
From: "Victor S. Miller" <VICTOR@yktvmz.bitnet>
Subject:      On the complexity of maintaining partial sums

Given an array A(i) initialized to 0, we consider a sequence of operations
UPDATE(a,i): add a to A(i)
QUERY(j): return sum(i=1 to j) A(i)
     
It is fairly easy to see that if the number of elements of the array
is N and the number of operations is M, we can do it in time O(M log N)
(by building a binary tree of intermediate partial sums, for example).
In a paper "On the Complexity of Maintaining Partial Sums" (published
as IBM Tech Rept RJ3228, and probably elsewhere, but I don't know the
reference), Andrew Yao showed that there is a lower bound of
Omega (N log N / log log N) if M  = O(N).  This result dated from 1981.
Has there been any progress on tightening the upper and lower bounds
since then?
                   Victor Miller -- IBM Research