THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE

Given an array A with n entries in an additive semigroup, and m intervals of the form Ii=[i,j], where 0semigroup additions. Here, α is the functional inverse of Ackermann's function. A matching upper bound has already been demonstrated.