2006/01/18 by Andrej Brodnik, Brodnik, Andrej, Johan Karlsson +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #E.1 #F.1.1 #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Natural Language Processing Techniques #cs.CC #cs.DS #cs.IR
paper · pdf · doi:10.48550/arxiv.cs/0601081
12 pages
arxiv created 2006/01/18 · openalex publication_date 2006/01/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Θ(\lg N) time under the comparison based model of computation.