170
правок
Изменения
м
Нет описания правки
Во-первых, мы должны запомнить для каждой вершины нашего изначального дерева поиска дополнительную информацию: <tex>minChild</tex> {{---}} минимальное значение в поддереве текущей вершины, <tex>maxChild</tex> {{---}} максимальное значение в поддереве.
Во-вторых, нам понадобятся операции [[Splay -дерево | split]] и [[Splay -дерево | merge]], которые работают за <tex>O(\log k)</tex>, где <tex>k</tex> {{---}} число узлов в <tex>splay</tex>- дереве.
Пусть для того, чтобы найти вершину <tex>x</tex>, которая находится в дереве <tex>F</tex>, мы прошли по тонкому ребру из вершины <tex>t</tex>, находящейся в дереве <tex>A</tex>.
