Изменения
→Сверхбыстрый цифровой бор (y-fast-trie)
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x-fast-trie</tex>. Всего в <tex>x-fast-trie</tex> будет <tex>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x{-}fast{-}trie</tex> будет занимать <tex>O(n)</tex> памяти.
Каждый лист <tex>x{-}fast{-}trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex>\frac{w}{2}</tex> До до <tex>2w</tex> элементов, поэтому его высота - <tex>O(\log w)</tex>.
Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x{-}fast{-}trie – O(n)</tex> памяти. Поэтому <tex>y{-}fast{-}trie</tex> тоже занимает <tex>O(n)</tex> памяти.
