Operácie
Pozrime sa teraz, ako budú prebiehať jednotlivé operácie.
1. Zmena hodnoty prvku
Keď chceme zmeniť hodnotu prvku $p_i$, zmeníme hodnotu v príslušnom liste nášho stromu. Okrem toho potrebujeme ešte aktualizovať všetkých jeho nadriadených, lebo aj im sa zmenil súčet úseku, za ktorý sú zodpovední. To budeme robiť odspodu:
- Najprv sa pozrieme na otca $o_1$ vrcholu $p_i$ a aktualizujeme ho (priradíme doňho súčet jeho synov). V tomto vrchole je teraz už správna hodnota.
- Následne sa pozrieme na otca $o_2$ vrcholu $o_1$ (teda deda vrcholu $p_i$) a aktualizujeme ho (rovnako ako predtým, priradíme doňho súčet jeho synov). Keďže obaja jeho synovia mali správne hodnoty (vrchol $o_1$ je už aktualizovaný a druhého syna nebolo treba aktualizovať), vypočítaná nová hodnota vrcholu $o_2$ bude tiež správna.
- Pokračujeme otcom vrchola $o_2$, potom jeho otcom atď. až kým neprídeme do koreňa.
Keď už aktualizujeme aj koreň, všetci predkovia (nadriadení) vrcholu $p_i$ si budú pamätať správnu aktuálnu hodnotu a náš strom bude pripravený na ďalšie použitie. Keďže náš strom má $\lg n + 1$ úrovní, vrchol $p_i$ má $\lg n$ predkov, teda celá aktualizácia prebehne v čase $O(\lg n)$.
Všimnime si, že aktualizácia sa dá robiť aj inak: môžeme si vypočítať, o koľko sme zväčšili číslo $p_i$ a následne o rovnaké číslo zväčšiť všetkých jeho predkov (pričom je jedno v akom poradí ich zväčšujeme, pokojne to môžeme
robiť aj zhora nadol). Takáto aktualizácia sa však nedá robiť vo všetkých druhoch intervalových stromov — pri súčtovom funguje, ale napríklad pri minimovom nie. Preto je lepšie poznať predošlý spôsob.
2. Súčet prvkov z intervalu
Opäť použijeme našu paralelu s úradníckou hierarchiou. Od každého úradníka budeme chcieť, aby vedel odpovedať na otázky typu "Aký je súčet čísel, ktoré sú v tvojom úseku a majú indexy z intervalu $[l, r)$ ?" To vie úradník zodpovedný za nejaký úsek $[x, y)$ urobiť nasledovne:
- Ak všetky prvky z $[x, y)$ ležia mimo $[l, r)$ (teda tieto dva intervaly sa neprekrývajú), potom odpovie 0.
- Ak všetky prvky z $[x, y)$ ležia v $[l, r)$, potom je odpoveď súčet všetkých čísel s indexami z $[x, y)$. A tento súčet si predsa náš úradník pamätá.
- Ak nenastane žiadna z predošlých možností (teda niektoré prvky z $[x, y)$ ležia v $[l, r)$ a niektoré nie), potom túto ťažkú otázku úradník v duchu zákona padajúceho exkrementu deleguje na svojich podriadených. Oboch svojich podriadených sa spýta, aký je súčet prvkov z ich úsekov, ktoré ležia v intervale $[l, r)$. Keďže úseky jeho podriadených akurát pokrývajú jeho úsek, stačí mu potom ich odpovede sčítať a dostane svoju odpoveď.
Všimnime si, že pri listoch tretí prípad nikdy nenastane — každý list si totiž pamätá iba jeden prvok, ktorého
index buď je, alebo nie je v $[l, r)$. Vďaka tomu sa nemôže stať, že by niekto, kto nemá podriadených, chcel delegovať svoju robotu na podriadených.
Správanie jednotlivých úradníkov sa dá ľahko implementovať ako rekurzívna funkcia. Keď chceme zistiť súčet prvkov s indexami z nejakého intervalu $[l, r)$, stačí sa na tento súčet spýtať koreňa (ktorý má na starosti celú
postupnosť $p_0, p_1, \dots, p_{n-1}$), teda zavolať z neho našu rekurzívnu funkciu.
Aké rýchle to bude? Časová zložitosť bude úmerná počtu vrcholov, do ktorých sa naša funkcia postupne rekurzívne zavolá, keďže okrem rekurzívnych volaní v každom vrchole urobíme iba konštantne veľa práce (overíme, či nastala niektorá z prvých dvoch podmienok a prípadne ešte sčítame výsledky zo synov). Všimnime si, že na každej úrovni našej hierarchie budú najviac dvaja úradníci, ktorí svoju otázku delegujú na podriadených: ten, v ktorého úseku je ľavý koniec intervalu $[l, r)$ a ten, ktorý má vo svojom úseku pravý koniec intervalu $[l, r)$. U všetkých ostatných úradníkov z rovnakej úrovne, na ktorých sa naša rekurzívna funkcia zavolá, nastane buď prvý, alebo druhý prípad. Ak niektorý z koncov intervalu $[l, r)$ sadne presne na hranicu medzi úsekmi dvoch úradníkov, bude delegujúcich úradníkov na tejto úrovni ešte menej.
To ale znamená, že na každej úrovni budú najviac štyria úradníci, do ktorých sa naša funkcia zavolá — podriadení úradníkov z úrovne o 1 vyššie, ktorí delegovali svoju otázku. Keďže náš strom má $\lg n + 1$ úrovní, dokopy sa naša rekurzívna funkcia zavolá najviac v $4 (\lg n + 1)$ vrcholoch, teda časová zložitosť celej operácie bude $O(\log n)$.
V konečnom dôsledku sme vlastne našli $O(\log n)$ úradníkov, ktorých intervaly dokopy dávajú interval $[l, r)$ a sčítali
sme čísla v nich. Celá mašinéria s hierarchiou a delegovaním povinností nám slúžila iba na to, aby sme ich našli efektívne a pohodlne. Je dobré si všimnúť, že úradníci, ktorých hodnty sme sčítali rozložia daný interval $[l, r)$ na $O(\log n)$ neprekrývajúcich sa intervalov, ktoré spolu pokrývajú celý interval $[l, r)$.