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.
User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Heavy Light Descomposition

Postby isaac » Wed Oct 28, 2015 3:44 pm

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: Heavy Light Descomposition

Postby HaZard » Fri Oct 30, 2015 6:21 pm

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: Thu Dec 08, 2011 12:02 pm
Gender: Male

Re: Heavy Light Descomposition

Postby WIL » Tue Feb 02, 2016 9:05 pm

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!!!


Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest