Изменения

Улучшим структуру: было два слабых места — подниматься вверх и искать минимум.

Первая модификация - занесем все элементы в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию succOrPred, которая возвращает следующий или предыдущий в зависимости от того, что проще. Спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага сможем получить ответ на запрос.

Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве.

При вставке с помощью succOrPred и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины(у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.

Удаление происходит аналогично.

Вставка и удаление выполняются за O(w).

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