Compressing Dynamic Fully Indexable Dictionaries in Word-RAM

Abstract

We study the problem of constructing a dynamic fully indexable dictionary (FID) in the Word-RAM model using space close to the information-theoretic lower bound. A FID is a data-structure that encodes a bit-vector $B$ of length $u$ and answers, for $b\in \{0,1\}$, ${\text{rank}}_b(B,x)=|\{y\le x|B[y]=b\}|$ and ${\text{select}}_b(B,r)=\min \{0\le x<u|{\text{rank}}_b(B,x)=r\}$ ($-1$ if empty). A dynamic FID supports updates that modify a single bit of $B$, i.e., $B[i]\leftarrow b$. We work in the Word-RAM model with $w$-bit words, assuming $w\ge \lg u$. Integer multiplication takes $\mathcal{O}(1)$ time. Our memory model is ${\mathcal{M}}_B$, allowing access to a fixed precomputed table of $\tau =\mathrm{polylog}(w)$ words, which can be computed in $\mathcal{O}(w\tau )$ time. In this paper, we show a dynamic FID based on the famous fusion-tree data-structure of P{ă}tra{ş}cu and Thorup [FOCS 2014], modified to use fewer bits and to support ${\text{select}}_0$. Let $n$ denote the number of ones in $B$. We describe a parametric construction: for every $\epsilon \le 1/2$, there is a dynamic FID using $$\lg \left(\genfrac{}{}{0ex}{}{u}{n}\right)+\mathcal{O}(n{w}^{\epsilon }/\epsilon )\text{ bits}$$ taking $\mathcal{O}(1/\epsilon +{\log }_w(n))$ time for ${\text{rank}}_0/{\text{rank}}_1/{\text{select}}_0$ and updates, and $\mathcal{O}({\log }_w(n))$ time for ${\text{select}}_1$. All time bounds are worst-case. For $\epsilon =1/\sqrt{\lg w}$, we reduce the space to $\lg \left(\genfrac{}{}{0ex}{}{u}{n}\right)+\mathcal{O}(n\log w)$ bits. For $\epsilon =\Theta (1)$, the running time matches the lower bound of Fredman and Saks [STOC 1989]. This is the first deterministic dynamic FID in the standard Word-RAM model that achieves $o(n\sqrt{w})$ bits of redundancy in ${\mathcal{M}}_B$ (e.g., $\epsilon =1/4$), and optimal worst-case time.

25 pages; To appear at STOC'26