2 papers
cs.DS2019
Partial Sums on the Ultra-Wide Word RAM
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
We consider the classic partial sums problem on the ultra-wide word RAM model of computation. This model extends the classic -bit word RAM model with special ultrawords of lengt…
cs.DS2017
Succinct Partial Sums and Fenwick Trees
Philip Bille, Anders Roy Christiansen, Nicola Prezza +1
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 ef…