Изменения

Пусть union(v1,v2) - процедура слития двух множеств содержащих v1,v2, а get(v) - поиск корня поддерева содержащего x. Рассмотрим n операций union и m операций get. Для удобства и без потери общности будем считать что у нас union принимает в качестве аргументов корни поддеревьев и (m>n), то есть (union(v1,v2) заменяем на union(get(v1),get(v2)). Тогда нам надо оценить стоимость операции get(v). Обозначим <tex>R(v)</tex> - ранг вершины,<tex>P(v)</tex> - отец вершины,<tex>L(v) </tex> - первой самый первый отец вершины.

Предположим на секунду, что Из того как работает функция get следует:1.<tex>\sum a_n^+R(L(v))>R(v) </tex> сходится2. Но Между <tex>a_n^- = a_n^+ - a_nv </tex>. Тогда, по линейности рядов, начнёт сходиться и ряд <tex>\sum a_n^-P(v) </tex>. Тогда, по линености рядов, так как существует путь вида : <tex>|a_n| = a_n^+ + a_n^v -> L(v) -> L(L(v)) ... ->P(v) </tex>, начнёт сходиться и ряд Записав неравенство из первого пункта вдоль пути из второго пункта следует что <tex>\sum |a_n|R(P(v))>R(v) </tex>. Противоречие.