Изменения
→Идея алгоритма
# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы простым путем, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве ближе к корню.
# Если дерево {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево ]], высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>
Тогда, представив данное дерево как полное [[Дерево поиска, наивная реализация|двоичное дерево]], в некоторых вершинах которого находится простой путь, можно научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.
