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