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