Изменения

перестройка = (<tex>(3 \cdot split + 3 \cdot merge) \cdot K = (O(1) + 3 \cdot O(\log \log n) + 3 \cdot O(\log \log n)) \cdot K </tex> = <tex>O(\log \log n \cdot OPT_{dyn} ) </tex>, где <tex>K</tex> {{---}} число изменений жирного ребра.