arvind@utcsri.UUCP (11/23/87)
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