Изменения

Заведем ==Описание структуры==Для хранения Rope создадим структуру, похожую на [[Дерево поиска, наивная реализацияДекартово дерево по неявному ключу|двоичное декартово дерево поискапо неявному ключу]]. В каждом листе будем хранить последовательную часть строки и ее длину, а в промежуточных вершинах будем хранить сумму длин всех листьев в поддереве. Изначально дерево состоит из одной вершины {{---}} сама строка. Используя информацию в промежуточных вершинах, можно получать символы строки по индексу, как будет показано ниже. Также заметим, что для отметки листа необязательно хранить дополнительную информацию: все внутренние вершины имеют ровно двух детей, а листы {{---}} не одного. Поэтому для проверки вершины на то, что она является листом, достаточно проверить, есть ли у неё дети.