Дерево

Таки реализовал порядковую статистику с поиском минимума на отрезке.
Декартовы деревья (они же дерамиды, они же treap, они же cartesian tree, они же деревья приоритетного поиска (по Вирту)) рулят. Смесь дерева и пирамиды. Дерево - для поиска, свойства кучи - для балансировки (у каждого узла есть дополнительный признак - приоритет, выбирается рандомом - по которому имеется свойства кучи). Вставка/удаление/поиск - как дерево, балансировка - как куча (два тривиальных поворота).

В Б-дереве удаление (точнее, сжатие узлов при удалении) - штука довольно нетривиальная при реализации.

Правда, поиск минимума на отрезке тривиален только первоначально в голове, при первой реализации поймаете "кучку" (в смысле множества) тонкостей. Советую нарисовать полный хип на 31/63 узла и потренироваться на "кошках". Порядковая статистика отличается от порядковой статистикой с поиском агрегата, только дополнительным методом для поиска всего-этого и тривиальным вызовом при поворотах для обновления агрегата.

На Б-дереве (с плотностью более 2) поиск минимума будет еще не тривиальнее.

Странно, все влезло в 10К. Теперь стоит написать комментарии, вынести минимум в сущность моноида и еще пара моментов. В 15К точно буду.

Update:
Дженерики более второго порядка в современном программировании - зло.
Как же называется коммутативная полугруппа? Моноид - не то, промахнулся я с абстракцией. Абелевы полугруппы? В мое время были только абелевы группы, let it be...
Вынес сущность, на (min, +\inf) все работало, на (+, 0) перестало. Где-то дважды хожу по дереву. Все не тривиальнее и не тривиальнее...

Update2:
забыл я алгебру... это просто коммутативный моноид.