Изменения
Rope
,Нет описания правки
Заведем двоичное сбалансированное дерево поиска. В каждом листе будем хранить последовательную часть строки. Изначально дерево состоит из одной вершины - сама строка.
==Merge==
Когда приходит запрос на конкатенацию с другой строкой мы объединяем оба дерева, создав новый корень и подвесив к нему обе строки.
<pre>
merge(T1, T2):
Node node
node.left = T1
node.right = T2
return node
</pre>
Асимптотика выполнения операции конкатенации двух строк очевидно <tex>O(1)</tex>.
==Получение символа по индексу==
return node.s[i]
</pre>
Асимптотика выполнения одного такого запроса очевидно <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
==Split==
Чтобы разбить строку на две по некоторому индексу <tex>i</tex> необходимо спускаясь по дереву(аналогично операции <tex>get</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.
<pre>
split(node, i):
Node t1, t2
t1.w = i
t2.w = node.w - i
Pair res
if (!isNil(node)):
if (node.left >= i):
res = split(node.left, i)
t1.left = res.first
t2.left = res.second
t2.right = node.right
else:
res = split(node.right, i - node.left.w)
t1.left = node.left
t1.right = res.first
t2.left = res.second
else:
t1.s = node.s.substr(0, i)
t2.s = node.s.substr(i, s.len)
return pair(t1, t2)
</pre>
Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>O(h)</tex>, где <tex>h</tex> - высота дерева.
==Операции удаления и вставки==
