An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture

Andrej Brodnik, Johan Karlsson, J. Ian Munro +1

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 mod…