De ce contează?
Imaginează-ți o firmă cu birouri pe șase etaje. Vrei să afli repede câți angajați sunt între etajele 2 și 5. Ai putea număra om cu om — dar firma are un „organigram": fiecare șef ține deja totalul subordonaților lui. Șeful general știe totalul firmei, doi vicepreședinți țin câte jumătate, și tot așa până la fiecare angajat. Ca să răspunzi, combini câteva totaluri gata calculate, nu toți oamenii. Un segment tree e exact această organigramă peste un șir: un arbore în care fiecare nod ține răspunsul unui interval — rădăcina tot șirul, frunzele câte un element.
Intuiția
Ai un șir și vrei două lucruri deopotrivă rapide: suma pe un interval
[l, r] și modificarea unui element. Un segment tree e un arbore binar peste
intervale: rădăcina acoperă tot șirul [0, n-1], fiecare nod cu intervalul
[st, dr] are doi copii care îl taie în jumătate — [st, mid] și
[mid+1, dr] — iar frunzele sunt elementele individuale. Fiecare nod ține deja
suma intervalului său. Atunci o interogare nu mai parcurge tot intervalul: coboară
și „lipește" câteva noduri gata calculate care acoperă exact [l, r].
Fiecare nod „răspunde" de exact un interval. Orice interogare [l, r] se
sparge, pe fiecare nivel, în cel mult 2 noduri noi — O(log n) noduri în
total, nu r - l + 1 elemente. Iar un update atinge doar lanțul
strămoșilor frunzei modificate: tot O(log n). De aici vin ambele viteze.