Computing partial sums in multidimensional arrays

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 = [a₁, b₁] x. x [ad, bd], compute the sum o(A, q) = σ A[k₁,..,k_d.(k₁ k₁)Eq . This problem comes in two distinct flavors. In query mode, preprocessing is allowed and q is a query to be answered on-line. In &line mode, we are given the array A and a set of d-rectangles q₁, . . . , q_m, and we must compute the m sums a(A,qi). Partial-sum is a special case of the classical orthogonal range searching problem: Given n weighted points in d-space and a query d-rectangle q, compute the cumulative weight of the points in q (see e.g. [3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 18, 19, 20, 21, 221). The dynamic version of partial-sum in query-mode was studied by Fredman [IO], who showed that a mixed sequence of n insertions, deletions, and queries may require n(n logd n) time, which is optimal (Willard and Lueker [20]). This result was partially extended to groups by Willard in [19]. For the case where only insertions and queries are allowed, a lower bound of n(n log n/log log n) was proven in the one-dimensional case (Yao [22]), and later extended to Q(n(log n/ log log R)~), f or any fixed dimension d (Chazelle [S]). Regarding static one-dimensional partial-sum, Yao proved that if m units of storage are used then any query can be answered in time O(a(m,n)), which is optimal in the arithmetic model [21]. The function a(m, n) is the functional inverse of Ackermann s function defined by Tarjan [15]. See also Alon and Schieber [2] for related upper and lower bounds. Our main results are a nonlinear lower bound for onedimensional partial-sum in off-line mode and a space-Time Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1989 ACM O-89791-318-3/89/0006/0131 $1.50 tradeoff for partial-sum in query mode in any fixed dimension. More precisely, we prove that for any n and m, there exist m partial sums whose evaluations require 0 (n + ma(m, n)) t ime. This is a rare case where the function a arises in an off-line problem. Noticeable instances are the complexity of union-find (Tarjan [15]) and the length of Davenport-Schinzel sequences (Hart and Sharir [ll], Agarwal et al. [l]). Interestingly, the proof technique we use does not involve reductions from these problems. Our result implies that, given a sequence of n numbers, computing partial sums over a well-chosen set of n intervals requires a nonlinear number of additions. This might come as a surprise in light of the fact that there is a trivial linear-Time algorithm as soon as we allow subtraction. The lower bound can be regarded as a generalization of a result of Tarjan [16] concerning the off-line evaluation of functions defined over the paths of a tree. As in [16] our result also leads to an improved lower bound on the minimum depth of a monotone circuit for computing conjunctions. The other contribution of this paper is an algorithm which can answer any partial-sum query in time O(α^dd(m,n)), where m is the amount of storage available. This generalizes Yao s one-dimensional upper bound [21] to fixed arbitrary dimension d. Since our algorithm works on a RAM, we can use it as the inner loop of standard multidimensional searching structures. For example, consider the classical orthogonal range searching problem on n weighted points in d-space. Lueker and Willard [20] have described a data structure of size O (nlog^d-1 n) which can answer any range query in time O((α^dn) (over a semigroup). We improve the time bound to O(log^d n). The remainder of this. abstract is devoted to the proofs of the lower and upper bounds. Except for a few technical lemmas whose proofs have been omitted, our exposition is complete and self-contained.