THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE

Authors:

Abstract
Given an array A with n entries in an additive semigroup, and m intervals of the form Ii=[i,j], where 0<i<j≤n, we show that the computation of A[i]+⋯+A[j] for all Ii, requires Ω(n+mα(m,n)) semigroup additions. Here, α is the functional inverse of Ackermann's function. A matching upper bound has already been demonstrated.