Декартово дерево по неявному ключу

Напомним, Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу.

Постановка задачи

Стандартное декартово дерево (или любое другое сбалансированное дерево поиска, мы будем рассматривать именно это применение декартовых деревьев) позволяет нам совершать практически любые операции, собственно, вставить или удалить элемент. Попробуем расширить список действий, которые мы хотим уметь делать. Основной принцип расширения можно описать так : взять элементы с порядковыми номерами от [math]l[/math] до [math]r[/math] и что-нибудь с ними сделать(вырезать, переставить, добавить ко всем числам на отрезке, развернуть, ....