Декартово дерево, задача RMQ

Построение декартова дерева за линейное время при предварительно отсортированных ключах, доказательство логарифмической оценки на глубину в среднем, основные операции через split и merge.

Решение задачи RMQ методом разреженной таблицы.