Ancestro común más bajo

Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)).

Tarjan también encontró un simple, pero menos eficiente algoritmo, basado en la estructura de datos conjuntos disjuntos.

Ellos entonces manipularon este problema mínimo valor en un rango combinando dos técnicas, una técnica basada en precomputar las preguntas en intervalos largos que tienen tamaño potencias de dos, y la otra basada en una tabla para buscar en intervalos pequeños.

Este método fue presentado más tarde en una forma simplificada por Michael Bender y Martin Farach-Colton en el 2000.

Como fue previamente observado por Gabow, Bentley y Tarjan en 1984, el problema del mínimo en un rango puede ser transformado hacia atrás en el problema del ancestro común más bajo usando la técnica de árboles cartesianos.