Вот мой код, реализующий декартово дерево по неявному ключу с массивом и номерами элементов массива вместо указателей. Думаю, с указателями решение будет всё-таки лучше, но мне такое решение интуитивно более понятно.
http://pastebin.com/HKSBNqZP
Этот код является решением задачи о переворотах детей в ряду и их сумме роста на интервале.