Изменения
→Способы реализации структуры
===Сбалансированное дерево поиска===
Будем хранить последовательности последовательность вершин эйлерова обхода в виде сбалансированного двоичного дерева поиска, например, в виде [[Красно-черное дерево|красно-черного дерева]]. При построении дерева ключом вершины будет время посещения этой вершины эйлеровым обходом.
Операции объединения и разделения красно-черных деревьев выполняется за <tex>O(\log n)</tex><ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf Ron Wein {{---}} Efficient Implementation of Red-Black Trees.]</ref>.
===Декартово дерево по неявному ключу===
Также, можем хранить последовательности вершин эйлерова обхода в [[Декартово_дерево_по_неявному_ключу|декартовом дереве по неявному ключу]]. Глубина декартового дерева, построенного на массиве из n вершин, будет поддерживаться lognравной <tex>O(\log n)</tex>. Операции объединения и разделения так же выполняются за <tex>O(\log n)</tex>.
==См. также==
