Декартово дерево

Для начала почитайте про двоичные деревья поиска, ну или еще здесь. Вам не обязательно (пока) уметь их писать, но просто поймите, что это такое и с чем его едят.

Теория на e-maxx
Теория на сайте ИТМО
Еще какая-то теория
Еще какая-то теория
Можете еще погуглить