Эффективно найти средний элемент в set'е

{1} => 1
{1,2} => 1 или 2
{1,2,3} => 2
{1,2,3,4} => 2 или 3 (но в ту же сторону от середины, что и с {1,2})
{1,312,10000,14000,152333} => 10000

Или, если все-таки использовать set, то можно поддерживать итератор, указывающий на медианный элемент и число элементов k до этого итератора.

• Изначально set пустой, итератор равен set.end(), k равно нулю
• При добавлении элемента в set:
  • новый элемент больше медианного => при необходимости (если k * 2 + 3 <= set.size()) сдвигааем итератор на один вперед и увеличиваем k на единицу.
  • новый элемент меньше медианного => при необходимости сдвигааем итератор на один назад и уменьшаем k на единицу.
• При удалении элемента из set действуем аналогично, при необходимости двигаем итератор на единицу вперед/назад
• Таким образом, в любой момент времени у нас есть итератор на медианный элемент, дополнительные расходы для поддержания этого итератора составляют O(log n) на каждую операцию вставки/удаления

И еще вот полезный вопрос на английском Stack Overflow примерно про это же (там без удаления, но идея такая же)

Если писать свое декартово дерево не хочется, то можно использовать встроенную в gcc структуру данных rope

Думаю, что нет. Ну смотрите, для поиска минимума в BST нужно всегда идти в левую ветку, максимума - в правую. И вот хотите Вы найти средний. И с самого начала неизвестно, что делать. Условно, у вас в корне дерева стоит "10", больше Вы ничего не знаете о содержимом. Куда пойдете?