The design of data structures and algorithms maintaining a sequence of elements from an arbitrary commutative semigroup, subject to addition updates and prefix-sum queries, has been studied under different models. We present a new such model. It uses a couple of arrays to describe the algorithms which implement the operations. The model includes optimal solutions in terms of amortized complexity.

lower bounds on complexity data structures, semigroup model, partial sums.