  In this paper we study the Prefix Sum problem introduced by Fredman.
  We show that it is possible to perform both update and retrieval in O(1) time
simultaneously under a memory model in which individual bits may be shared by
several words.
  We also show that two variants (generalizations) of the problem can be solved
optimally in $\Theta(\lg N)$ time under the comparison based model of
computation.
