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

Simple item page
dc.creatorBrodnik, Andrej
dc.creatorKarlsson, Johan
dc.creatorMunro, J. Ian
dc.creatorNilsson, Andreas
dc.date2006-01-18
dc.date.accessioned2026-07-07T06:57:58Z
dc.date.available2026-07-07T06:57:58Z
dc.descriptionIn 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.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/cs/0601081
dc.identifierhttp://arxiv.org/abs/cs/0601081
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/107178
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.subjectInformation Retrieval
dc.subjectE.1; F.1.1
dc.titleAn O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
dc.typetext

Files

Collections

arXiv