The \(O(w)\)  term in the space bound above is due to the \(w\) -parallel dictionary \(D\)  and \(O(1)\)  ultraword constants. To avoid this when \(n = o(w)\) , we will initially support \(\mathsf {predecessor}\) , \(\mathsf {insert}\)  and \(\mathsf {delete}\)  using the dynamic fusion tree by Pătraşcu and Thorup [1]} (based on the fusion tree by Fredman and Willard [2]}), which uses linear space and supports all three operations in constant time for sets of size \(w^{O(1)}\) . Simultaneously, we build the ultraword constants we need over the course of \(\Theta (w)\)  insertions, maintaining linear space. When \(n \ge w\) , the constants have been built and we move all elements into the trie. If at any point \(n \le w/2\) , we move all elements from the trie into a fusion tree and remove the trie and the ultraword constants, leaving us with linear space and \(\Theta (w)\)  \(\mathsf {insert}\)  operations in which to rebuild the constants. Updates still run in amortized expected constant time since we always do \(\Theta (w)\)  updates before we move \(O(w)\)  elements.
