Preprint
Aug 2026
Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space
We show how to implement a dynamic array $A[1, n]$ with symbols from a fixed alphabet $\Sigma$, while supporting $O(1)$-time queries and updates, and using a total space of $$ \log \binom{|\Sigma|}{m} + \left(1 + O\left(\frac{\log \log n}{\log n}\right)\right) \cdot \left(\sum_{\sigma \in \Sigma} f_\sigma \log (n / f_\...
G. Blelloch, Yang Hu, William Kuszmaul et al.
· 2 citations