De ce contează?
Vizitezi un muzeu cu săli băgate una într-alta: sala mare conține săli mai mici, care conțin altele și mai mici. Porți un ceas și notezi două momente pentru fiecare sală: când intri prima oară în ea și când ieși definitiv din ea. Observația de aur: tot ce ai vizitat între cele două momente se află în interiorul acelei săli — nimic din afară nu se poate strecura în notițele tale. Exact așa „desfășori” un arbore pe o linie: sălile sunt noduri, iar fiecare subarbore devine o bucată continuă din jurnalul vizitei.
Ce este
Un subarbore e o structură 2D: se ramifică. Dar dacă numerotezi nodurile în
ordinea în care un DFS le vizitează prima oară, descendenții oricărui nod u
primesc numere care formează un bloc neîntrerupt. Motivul e simplu: DFS-ul, odată
ce a intrat în u, nu iese din subarborele lui până nu l-a parcurs complet — deci
toate numerele „dintre” intrarea și ieșirea din u aparțin subarborelui lui u.
Concret, reținem pentru fiecare nod v două momente de „ceas”: tin[v] —
momentul primei intrări în v — și tout[v] — momentul la care DFS-ul a
terminat complet subarborele lui v. Perechea asta e tot ce ne trebuie.
Subarborele lui v = intervalul contiguu [tin[v], tout[v]] în ordinea DFS.
Arborele devine un vector: orice problemă „pe subarbore” (sumă, minim, numărare)
devine o problemă „pe interval” — iar pentru intervale avem deja unelte rapide
(Fenwick tree, segment tree).
Vrei să răspunzi la întrebări de tipul „care e suma valorilor din subarborele lui
u?”. Prima idee: la fiecare întrebare pornesc un DFS din u, vizitez tot
subarborele și adun valorile.
Un subarbore poate avea aproape n noduri, deci o singură întrebare costă O(n).
La q întrebări ajungi la O(n·q) — pentru n și q de ordinul 100000, sunt
miliarde de operații. Mult prea lent.
Fac un singur DFS care notează, pentru fiecare nod, momentul de intrare
tin[v] și momentul de ieșire tout[v]. Cheia: orice nod w din subarborele
lui v are tin[v] <= tin[w] și tin[w] <= tout[v]. Deci subarborele lui v
este exact mulțimea nodurilor cu tin în intervalul [tin[v], tout[v]] — un
interval contiguu pe linia Euler.
Liniarizez arborele printr-un DFS (o singură dată, O(n)). Apoi „suma pe subarbore”
devine „suma pe intervalul [tin[v], tout[v]]” — exact ce rezolvă un Fenwick tree
sau un segment tree în O(log n) pe întrebare.