THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
Bernard Chazelle, Burton Rosenberg · International Journal of Computational Geometry & Applications · 1991
Given an array A with n entries in an additive semigroup, and m intervals of the form Ii=[i,j], where 0i, requires Ω(n+mα(m,n)) semigroup additions. Here, α is the functional inverse of Ackermann's function. A matching upper bound has already been demonstrated.