Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space

Guy E. Blelloch, Yang Hu, William Kuszmaul +2

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 \bin…