An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
<|reference_start|>An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture: 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.<|reference_end|>
@article{brodnik2006an,
    title={An O(1) Solution to the Prefix Sum Problem on a Specialized Memory
  Architecture},
    author={Andrej Brodnik, Johan Karlsson, J. Ian Munro, Andreas Nilsson},
    journal={arXiv preprint arXiv:cs/0601081},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0601081},
    primaryClass={cs.DS cs.CC cs.IR}
}