2017/05/31 by Philip Bille, Anders Roy Christiansen, Bille, Philip +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1705.10987
openalex publication_date 2017/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be efficiently answered. We present two succint versions of the Fenwick Tree - which is known for its simplicity and practicality. Our results hold in the encoding model where one is allowed to reuse the space from the input data. Our main result is the first that only requires nk + o(n) bits of space while still supporting sum/update in O(logb n) / O(b logb n) time where 2 <= b <= logO(1) n. The second result shows how optimal time for sum/update can be achieved while only slightly increasing the space usage to nk + o(nk) bits. Beyond Fenwick Trees, the results are primarily based on bit-packing and sampling - making them very practical - and they also allow for simple optimal parallelization.