Изменения

Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве. [[File:TrieMin.jpg|thumb|left|300px200px|Ссылка на минимум]] [[File:Trie_max.jpg|thumb|300px200px|Ссылка на максимум]]

Пока что мы не добились асимптотического выигрыша - все операции по-прежнему выполняются за О(w). Теперь слабое место - это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в HashMap - ассоциативный массив, который по префиксу возвращает вершину в боре (чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида 0..01..1). Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину(у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за О(1) находим минимум или масимум, и за О(1) переходим по списку, если нужно.  Итого операции find, succ и pred будут выполняться за O(log w).