Pentru perechea de noduri ({$4, 3$}), avem {$lca(4, 3)$} egal cu nodul care se gaseste intre {$poz{~4~}$} si {$poz{~3~}$} in parcurgerea euler si are adancimea minima. Acest nod este $1$, deci {$lca(4, 3) = 1$}.

Am redus problema la aflarea minimului intre doua pozitii ale unui sir ({_Range Minimum Query_}). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {$i$}. Timpul de preprocesare este {~O(N)~} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.

Am redus problema la aflarea minimului intre doua pozitii ale unui sir ({_Range Minimum Query_}). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {$i$}. Timpul de preprocesare este {$O(N)$} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.

Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand: