Lazy propagation (alebo, ak chcete, lenivé šírenie informácie) je technika, pomocou ktorej dokážeme v intervalových stromoch spracúvať požiadavky typu ,,zmeň rovnakým spôsobom všetky prvky z intervalu $[l, r)$'' v čase $O(\log n)$.
Na to, čo všetko sa môže znamenať ,,zmeň rovnakým spôsobom'' sa poriadne pozrieme na konci tohto článku. Dovtedy sa budeme zaoberať jedným konkrétnym prípadom: súčtovým intervalovým stromom s požiadavkou ,,prenásob všetky prvky z intervalu $[l,r)$ hodnotou $v$''. Domyslieť, ako to bude vyzerať v iných prípadoch, už nechávame na čitateľovi.
Chceme napísať intervalový strom nad postupnosťou $p_0, p_1, \dots, p_{n-1}$, ktorý bude vedieť spracúvať
tieto tri druhy požiadaviek (všetky v čase $O(\log n)$):
Pre daný index $i$ a hodnotu $v$ zmeň prvok $p_i$ na $v$.
Pre dané indexy $l, r$ vypočítaj súčet všetkých prvkov s indexami z $[l, r)$, teda hodnotu
$p_l + p_{l+1} + \dots + p_{r-1}$. 3. Pre dané indexy $l, r$ a hodnotu $v$ prenásob všetky prvky s indexami z $[l, r)$ hodnotou $v$.
Môžeme si všimnúť, že prvú požiadavku v podstate ani nepotrebujeme, keďže sa na jednotlivé prvky vieme pozerať ako na jednoprvkové intervaly a zmeniť ich pomocou tretej požiadavky. Druhú požiadavku implementujeme úplne rovnako ako v texte o obyčajnom intervalovom strome, teda ako rekurzívnu funkciu, ktorú zavoláme do koreňa. Budeme sa teda sústrediť hlavne na to, ako vymyslieť tretiu požiadavku.
Pozrime sa najprv, ako sa dá tretí druh požiadaviek spracúvať menej efektívnym spôsobom.
Opäť použijeme paralelu s úradníkmi z textu o intervalovom strome. Každý vrchol stromu je teda úradník, ktorý má na starosti nejaký úsek postupnosti $p_0, p_1, \dots, p_{n-1}$ a pamätá si jeho súčet. Každý úradník, okrem listov, má dvoch priamych podriadených — svojich synov v strome. Každý z podriadených je zodpovedný za jednu polovicu úseku svojho šéfa.
Od každého úradníka teraz budeme chcieť, aby vedel spracúvať požiadavku ,,vynásob hodnoty všetkých prvkov z tvojho úseku, ktoré majú index z intervalu $[l, r)$ hodnotou $v$''. Úradníci, ktorí sa starajú iba o jeden prvok (teda listy nášho stromu) to majú jednoduché: pozrú sa, či jeho index leží v $[l, r)$ a podľa toho ho buď prenásobia $v$-čkom, alebo neurobia nič. Vyššie postavený úradník (teda nie list) to môže riešiť nasledovne:
Takéto správanie sa dá ľahko implementovať ako rekurzívna funkcia. Keď budeme chcieť prenásobiť prvky z nejakého intervalu nejakou hodnotou, stačí nám túto funkciu zavolať z koreňa. Jediný problém je, že takto napísaná funkcia bude pomalá — jej časová zložitosť bude $O((r - l) \log n)$, čo pre dlhé intervaly $[l, r)$ bude $O(n)$.