Poate povesti cineva puțin mai mult la ce se referă când zice "Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe" și cum se face update?
Iniţial, consideri cel mai lung lanţ (cu cele mai multe noduri) de la rădăcină la oricare din frunze. Reţii acest lanţ şi îl scoţi din arbore. Astfel, dacă lanţul ăsta „taie” arborele pe jumătate o să ai doi arbori separaţi pe care repeţi procedeul. Apelând recursiv rezolvi aceeaşi problemă. Şi vei reţine astfel o mulţime de lanţuri ce reprezintă descompunerea arborelui. Ulterior, pe ele faci operaţiile.
Query-urile se fac pe un arbore de intervale. Deci, un update din problemă se reduce la un update pe un arbore de intervale. Mai întreabă dacă nu ai înţeles.