Intervalový strom

Intervalový strom je dátová štruktúra, ktorá si, podobne ako obyčajné pole, pamätá postupnosť $n$ prvkov s indexami $0, 1, \dots, n-1$. Tieto prvky si pre jednoduchšie vyjadrovanie označme $p_0, p_1, \dots, p_{n-1}$. Intervalový strom dokáže robiť nasledovné operácie:

1. Pre zadanú hodnotu $h$ a index $i$ zmeniť hodnotu prvku $p_i$ na $h$, v čase $O(\log n)$.
2. Pre zadané $l, r$ (kde $0 \leq l \leq r < n$) odpovedať na otázku „aký je súčet čísel s indexami medzi $l$ a $r$?“ , v čase $O(\log n)$.

Ako ste si asi všimli, iba druhú operáciu vieme robiť aj pomocou prefixových súčtov. Intervalý strom nám umožňuje vypočítať na intervale aj operácie, ktoré pomocou myšlienky prefixových súčtov nevieme. Napríklad maximum, alebo minimum na intervale. Konkrétne na mieste druhej operácii môže byť namiesto sčítania ľubovoľná iná asociatívna operácia (napríklad súčin, maximum, minimum, najväčší spoločný deliteľ ...). Podľa toho potom hovoríme o súčtovom intervalovom strome, súčinovom intervalovom strome, maximovom intervalovom strome atď. Pre jednoduchosť sa budeme zaoberať súčtovým intervalovým stromom. To, ako vyzerajú tie ostatné, si už ľahko domyslíte.

S použitím techniky lenivého šírenia informácie sa dá napísať intervalový strom, ktorý podporuje navyše ešte tretiu operáciu:

3. Pre zadané $l, r$ (a prípadne nejaké ďalšie parametre) zmeň hodnoty všetkých prvkov s indexami medzi $l$ a $r$ rovnakým spôsobom, v čase $O(\log n)$ (všimnite si, že časová zložitosť nezávisí od počtu prvkov, ktoré meníme).

To, ako presne môžeme touto operáciou meniť prvky, závisí od typu nášho stromu. Pri súčtovom intervalovom strome napríklad môžeme mať operáciu, ktorá nám umožní všetky prvky s indexami medzi $l$ a $r$ zvýšiť o rovnakú zadanú hodnotu $c$.

Porovnanie s inými prístupmi

Ako sme už načrtli, rovnaké operácie ako s intervalovým stromom vieme robiť aj inými spôsobmi, s inými časovými zložitosťami.

Prvky našej postupnosti si môžeme napríklad pamätať v obyčajnom poli. Zmena prvku na danom indexe je potom v čase $O(1)$, čo je rýchlejšie ako intervalový strom. Vypočítanie súčtu čísel na intervale $[l, r)$ však môže trvať až $O(n)$, keďže nám neostáva nič iné, než prejsť všetky prvky medzi $l$ a $r$ a pekne po jednom ich sčítať.

Ak by sme si prvky pamätali v poli a okrem toho k nim mali ešte predpočítané prefixové súčty, súčty intervalov by sme vedeli počítať v čase $O(1)$. Zmena prvku by nás však stála čas $O(n)$ (keďže po zmene jedného prvku by sme museli prepočítať veľkú časť prefixových súm).

Ak teda jednu z našich dvoch operácií (zmenu prvku, alebo výpočet súčtu) potrebujeme robiť veľakrát a druhú skoro vôbec, je efektívnejšie použiť niektorý z týchto jednoduchších prístupov.