Изменения

merge('''Node''' T1, '''Node''' T2) = '''Node'''(T1, T2, T1.w + T2.w)

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

'''else''':

'''return''' node.s[i]

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

t2.s = node.s.substr(i, s.len)

'''return''' pair(t1, t2)

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

t1 = merge(t1, t3)

'''return''' merge(t1, t2)

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