Optimal biweighted binary trees and the complexity of maintaining partial sums

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update(j, x) has the effect A[j] <-- A[j] + x, and the query operation sum(j) returns the partial sum Sigma(i=1)(j) i=1 A[i]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semigroup model of computation. Our analysis relates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of biweighted binary tree.