3622
правки
Изменения
Нет описания правки
Уменьшим количество занимаемой памяти.
Пусть <tex>a_1 < a_2 < a_3 < ... < a_n</tex> {{---}} числа, которые нужно хранить в боре.
Выберем какое-то <tex>k</tex> (что за <tex>k</tex> {{---}} будет видно дальше). Разобьём их на <tex>s</tex> блоков <tex> B </tex> размером от <tex dpi=150>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее <tex>B_\overbrace {11a_1 < a_2 < a_3} < B_^{12B_1} ~\overbrace {a_4 < ... < B_}^{1n_{1B_2}} < B_~\overbrace {21} < ... < B_~a_{2n_{2}n-1} < ... < B_{s1a_n} < ... < B_{sn_^{s}B_s}</tex>
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x{-}fast{-}trie</tex>. Всего в <tex>x{-}fast{-}trie</tex> будет <tex dpi=150>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x{-}fast{-}trie</tex> будет занимать <tex>O(n)</tex> памяти.
