Изменения

Асимптотика выполнения операции конкатенации двух строк очевидно <tex>\mathrm{O(1)}</tex>.

Асимптотика выполнения одного такого запроса очевидно <tex>\mathrm{O(h)}</tex>, где <tex>h</tex> {{---}} высота дерева.

Чтобы разбить строку на две по некоторому индексу <tex>\mathrm{i}</tex> необходимо спускаясь по дереву (аналогично операции <tex>\mathrm{get}</tex>), каждую вершину на пути поделить на две, каждая из которых будет соответствовать одно из половинок строк, при этом необходимо после деления пересчитать вес этих вершин.

Тогда результатом выполнения операции <tex>\mathrm{split}</tex> по индексу 16 будет:

Заметим, что появляются лишние вершины, у которых есть только один потомок. От них можно легко избавится, просто заменив их на этого потомка. Тогда результатом той же операции <tex>\mathrm{split}</tex> будет:

Нетрудно заметить что асимптотическая сложность выполнения данной операции <tex>\mathrm{O(h)}</tex>, где <tex>h</tex> {{---}} высота дерева.

Нетрудно понять, что имея операция <tex>\mathrm{merge}</tex> и <tex>\mathrm{split}</tex>, можно легко через них выразить операции <tex>\mathrm{delete}</tex> и <tex>\mathrm{insert}</tex> по аналогии с другими деревьями поиска.

Операция <tex>\mathrm{delete}</tex> удаляет из строки подстроку начиная с индекса <tex>beginIndex</tex> и заканчивая (не включая) индексом <tex>endIndex</tex>.

Операция <tex>\mathrm{insert}</tex> вставляет данную строку <tex>s</tex> в исходную начиная с позиции <tex>insertIndex</tex>.

Так как данные операции используют только <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> то асимптотика времени их работы <tex>\mathrm{O(h)}</tex>, где <tex>h</tex> - высота дерева.

Предлагается хранить его как [[АВЛ-дерево]] и делать соответствующие балансировки. Тогда, так как высота АВЛ-дерева <tex>h = \log{n}</tex>, то асимптотика операций <tex> \mathrm{get, split, delete, insert, merge}</tex> будет равна <tex>\mathrm{O(\log{n})}</tex>, где <tex>n</tex> - количество сконкатенированных строк.