Heavy Light Descomposition

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
isaac
Posts: 83
Joined: 2 years ago
Gender: None specified

Heavy Light Descomposition

Post by isaac » 2 years ago

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



HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: Heavy Light Descomposition

Post by HaZard » 2 years ago

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
teruel

User avatar
WIL
Posts: 11
Joined: 6 years ago
Gender: Male

Re: Heavy Light Descomposition

Post by WIL » 2 years ago

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. :D :D :D

FIXED
Last edited by WIL on Wed Feb 03, 2016 4:23 pm, edited 1 time in total.
I'm interesting in learn!!!

Post Reply

Return to “Algorithms”