Изменения

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

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

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

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