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

Abstract

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 \left(\genfrac{}{}{0ex}{}{|\Sigma |}{m}\right)+\left(1+O\left(\frac{\log \log n}{\log n}\right)\right)\cdot \left(\sum _{\sigma \in \Sigma }{f}_{\sigma }\log (n/f_{\sigma })\right)+n/\text{polylog }n$$ bits, where $f_{\sigma }$ denotes the frequency of each symbol $\sigma \in \Sigma$ and $m$ denotes the number of distinct symbols with non-zero frequencies. This resolves a long-standing open question as to whether one can achieve space bounds close to that of arithmetic coding, while supporting $O(1)$-time operations, whenever the entropy is at least $n/\text{polylog }n$. We also prove a nearly matching space lower bound: up to a factor of $O(\log \log n)$, the entropy-dependent multiplicative overhead of our construction is optimal among $O(1)$-time solutions when $|\Sigma |=O(\sqrt{n})$ and the entropy ${\sum }_{\sigma \in \Sigma }{f}_{\sigma }\log (n/f_{\sigma })$ lies between $n/{\log }^{O(1)}n$ and $(1/100)n\log n$. Finally, we present several applications of our results, resolving two open problems having to do with space-efficient dictionaries and filters.

39 pages. In FOCS 2026