Изменения

Пока что мы не добились асимптотического выигрыша {{---}} все операции по-прежнему выполняются за <tex>O(w)</tex>. Теперь слабое место {{---}} это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в <tex> HashMap </tex> {{---}} [[Хеш-таблица |ассоциативный массив]], который по префиксу возвращает вершину в боре <tex>(</tex>чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида <tex>0...01...1\ldots01\ldots1)</tex>. Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину (у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за <tex>O(1)</tex> находим минимум или масимуммаксимум, и за <tex>O(1)</tex> переходим по списку, если нужно.