Computing partial sums in multidimensional arrays
Bernard Chazelle, Burton Rosenberg · 1989
1 Introduction The central theme of this paper is the complexity of the partial-sum problem: Given a d-dimensional array A with n entries in a semigroup and a d-rectangle q = [a1; b1] \\Theta \\Delta \\Delta \\Delta \\Theta [ad; bd], compute the sum oe(A; q) = X