Optimalizácia

Doteraz sme boli zvyknutí, že v listoch intervalového stromu sú uložené prvky $p_0, p_1, \dots, p_{n-1}$ postupnosti, ktorú daný strom reprezentuje a v každom vrchole je súčet prvkov úseku, za ktorý zodpovedá. Po optimalizácii, ktorú sa teraz chystáme spraviť, to už nebude vždy pravda. Niekedy bude v niektorých vrcholoch ,,nesprávna'' hodnota. Bude však platiť, že vždy, keď hodnotu nejakého vrcholu na niečo potrebujeme, bude si tento vrchol pamätať správnu hodnotu.

Všimnime si, že momentálne v našom strome platí nasledovné: Ak niekto od úradníka niečo chce, tak je to jeho šéf, ktorý naňho deleguje nejakú požiadavku. To nám umožní optimalizáciu tretieho druhu požiadaviek. Tá bude založená na

lenivosti našich úradníkov.

Občas sa nejakému úradníkovi stane, že mu príde požiadavka tretieho druhu (teda aby prenásobil prvky s indexami z $[l, r)$ hodnotou $v$) pre taký interval $[l, r)$, že celý jeho úsek leží v tomto intervale. Normálne by mal túto požiadavku delegovať na svojich podriadených a potom si aktualizovať svoju hodnotu. Náš úradník je však lenivý a nechce sa mu vstávať zo stoličky, aby mohol dať robotu svojim podriadeným. Preto si svoju prácu trochu uľahčí:

• Ak všetky prvky z jeho úseku prenásobíme hodnotou $v$, aj ich súčet sa zväčší $v$-násobne. Svoju hodnotu si teda náš úradník môže aktualizovať aj sám bez toho, aby si musel zisťovať nové hodnoty svojich podriadených.
• Namiesto toho, aby svojim podriadeným išiel povedať, že si majú všetky svoje prvky prenásobiť hodnotou $v$, si iba do svojho diára napíše poznámku, že by im to niekedy mal povedať.

Podriadení nášho úradníka sa teda nedozvedeli, že si mali zmeniť hodnoty a teraz majú zastaranú informáciu. To nevadí, kým od nich nikto nič nechce. Problém by nastal, keby im niekto dal nejakú požiadavku skôr, než sa ich šéfovi uráči povedať im, že mali zmeniť hodnoty vo svojich úsekoch. Našťastie v našom strome platí, že jediný, kto od nich môže niečo chcieť je ich šéf a ten si na to vie dať pozor:

• Ak úradník v rámci spracúvania nejakej požiadavky potrebuje niečo delegovať na svojich podriadených, najprv sa pozrie do svojeho diára, či im nemal niečo povedať. Ak zistí, že im mal povedať, aby všetky prvky vo svojich úsekoch prenásobili nejakou hodnotou $v$, tak im to najprv povie (a vyškrtne si to z diára) a až keď to spracujú, deleguje na nich robotu, ktorú im chcel dať.

Špecifická situácia nastane, ak od úradníka viackrát po sebe chceme, aby prenásobil všetky prvky svojho úseku nejakým číslom. Pri druhej (a každej ďalšej) takejto požiadavke po sebe si pôjde do diára zapísať, že má povedať svojim synom aby sa prenásobili nejakou hodnotou $v$. Pritom však zistí, že tam už má zapísané, aby im povedal, že sa majú prenásobiť nejakou staršou hodnotou $u$. V takom prípade jednoducho v diári nahradí hodnotu $u$ hodnotou $u \cdot v$, keďže prenásobiť číslo najprv hodnotou $u$ a potom hodnotou $v$ je to isté ako vynásobiť ho hodnotou $u \cdot v$.

Takéto správanie nám zaručí, že vždy, keď od nejakého úradníka niekto niečo potrebuje, tento úradník bude mať aktuálne

informácie. Vďaka tomu bude náš strom fungovať korektne napriek tomu, že niektorí úradníci si v niektorých momentoch

pamätajú zastaranú informáciu.

Zložitosť

Poďme sa teraz pozrieť na časovú zložitosť jednotlivých požiadaviek.

Vieme, že pri vyhodnocovaní druhej požiadavky voláme rekurzívnu funkciu, ktorá sa postupne zavolá do $O(\log n)$ vrcholov. Pri obyčajnom intervalovom strome v každom z týchto vrcholov urobila (okrem rekurzívnych volaní) $O(1)$ roboty, teda celková zložitosť bola $O(\log n)$.

Teraz sa v každom volaní našej funkcie môže navyše ešte stať, že úradník, do ktorého sme túto funkciu zavolali, potrebuje svojím podriadeným povedať, aby prvky vo svojich úsekoch prenásobili nejakou hodnotou (ktorú mal predtým zapísanú vo svojom diári). To však tiež trvá iba konštantný čas: náš úradník im to povie a oni (keďže sú tiež leniví) to už ďalej rekurzívne nehovoria svojim podriadeným, iba si aktualizujú svoju hodnotu

a zapíšu čosi do svojich diárov. Druhá operácia má teda stále časovú zložitosť $O(\log n)$.

S prvým druhom požiadaviek to bude veľmi podobne ako s druhou a tiež budú mať zložitosť $O(\log n)$.

Pri vyhodnocovaní tretieho druhu požiadaviek voláme do koreňa rekurzívnu funkciu. Táto funkcia okrem rekurzívnych volaní robí konštantne veľa práce (úradník musí zistiť, aký prípad nastal, aktualizovať si svoju hodnotu, v niektorých prípadoch zapísať niečo do diára a v iných prípadoch povedať svojim podriadeným aby sa prenásobili číslom, ktoré má v diári). Zložitosť našej funkcie teda bude úmerná počtu vrcholov, na ktoré sa rekurzívne zavolá. Ten však bude presne rovnaký, ako keby sme spracúvali požiadavku druhého druhu pre rovnaký interval ­— to, kedy sa funkcia rekurzívne rozvetví, sa riadi na základe rovnakých kritérií.

Preto aj vyhodnocovanie tretieho druhu požiadaviek bude mať zložitosť $O(\log n)$.