On the Complexity of Maintaining Partial Sums

Let F = \ ( rᵢ ,sᵢ )|0 i < n\ be a file of n records, where rᵢ are d-dimensional vectors and sᵢ are elements of a commutative semigroup S. We are interested in the partial sum problem, in which queries of the form “∑_rᵢ a sᵢ = ?” are to be answered. A space-time tradeoff t = Ω (log n/log (mlog n/ n) is established for storing a static two-dimensional file. It will also be shown that, for the one-dimensional problem, any dynamic algorithm must have a worst-case time Ω (nlog n/log log n) in processing a sequence $O(n)$ INSERT and QUERY instructions.