Изменения

Перейти к: навигация, поиск

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

993 байта добавлено, 08:17, 27 апреля 2011
Нет описания правки
Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу.
 
==Постановка задачи==
Стандартное декартово дерево (или любое другое сбалансированное дерево поиска, мы будем рассматривать именно это применение декартовых деревьев) позволяет нам совершать практически любые операции, собственно, вставить или удалить элемент. Попробуем расширить список действий, которые мы хотим уметь делать. Основной принцип расширения можно описать так : '''взять элементы с порядковыми номерами от <tex>l</tex> до <tex>r</tex> и что-нибудь с ними сделать(вырезать, переставить, добавить ко всем числам на отрезке, развернуть, ...'''.
40
правок

Навигация