2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/107178In 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 $Θ(\lg N)$ time under the comparison based model of computation.12 pagesData Structures and AlgorithmsComputational ComplexityInformation RetrievalE.1; F.1.1text