Heavy Light Descomposition

[isaac]

Alguno tiene una implementacion del Heavy Light Descomposition o al menos un razonamiento de como funciona y para que se puede emplear??

[HaZard]

Es una forma de descomponer un arbol en cadenas de modo que facilita hacer operaciones en los caminos dentro del arbol, un ejemplo sumar un valor a todos los nodos en el camino de A a B, pero en tiempo logaritmico. La base del algoritmo es la dp y es por lo menos nivel 4 en el COJ, el algoritmo te lo debo, Saludos

[WIL]

Para aprender sobre HLD, realmente recomiendo este artículo, porq intentar explicarlo mejor no creo q sea posible. Después de leerlo creo que si se tiene cierto nivel se puede implementar por uno mismo. Por ahí implementé mi 1er HLD.
PD. Es una locura intentar aprender HLD si antes no se han dominado conceptos básicos como recursividad, grafos, árboles y además se dominan estructuras de datos como segmenttree, RMQ o ABI, que son de gran usabilidad una vez q se aplica el HLD.

FIXED