Изменения

Напомним, ==Постановка задачи==Возьмем структуру данных '''[[Декартово деревоСаморасширяющийся массив|вектор]]''' {{---}} это структура данных. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента и изменить элемент по номеру, объединяющая и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в себе бинарное любое место (с соответствующим изменением нумерации элементов) и удалять любой элемент (с тем же самым уточнением). Теперь нам нужно придумать структуру, называемую '''Декартово дерево поиска и бинарную кучупо неявному ключу''', или же '''rope'''(англ.'''веревка''').

==Постановка задачиОсновная идея==Стандартное декартово Напомним, '''[[Декартово дерево (или любое другое сбалансированное ]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поискаи бинарную кучу. Для решения задачи, мы будем рассматривать именно это применение декартовых деревьев) позволяет нам совершать практически любые операции, собственнопоставленной в предыдущей главе, вставить или удалить элементпопробуем слегка модифицировать эту структуру. Попробуем расширить список действийЕсли конкретнее, которые мы хотим уметь делатьто оставим в нем только один ключ - ключ <tex>Y</tex>. Основной принцип расширения можно описать так Вместо второго ключа будем использовать следующую величину: '''взять элементы количество элементов в нашей структуре, находящихся левее нашего элемента'''. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу. Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с порядковыми номерами от этим подходом появляется две проблемы: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>lO(n)</tex> до времени, где <tex>rn</tex> и что{{---нибудь с ними сделать(вырезать, переставить, добавить ко всем числам на отрезке, развернуть, ...'''}} количество элементов в дереве.