Отсортированный массив, Как вставить в массив элемент за log n ? Опции

[krilov]

Нет ли способа вставить в отсортированный массив новый элемент за O(log n)?[size=3]

[hardcase]

А ты Красно-Чёрные деревья пробовал, ну или АВЛ-деревья?
Думаю должно прокатить, вот только я не помню время вставки-удаления.

А вот ещё вариант: у нас есть уже отсортированный массив чисел. При сумме двух минимальных мы пытаемся найти вхождение этого числа в массив - если не находим, то добавляем в список, ассоциированный с ближайшим меньшим/большим числом (соответственно список тоже должен быть отсортированным). В противном случае (если вхождение нашли) то инкрементим счётчик вхождений данного числа.
По моему это будет эффективно и должны уложиться в О(н*Лог(н)).