Štruktúra

Odteraz ďalej sa nám bude hodiť, aby počet prvkov $n$ našej postupnosti bola nejaká mocnina dvojky. V praxi, keď budeme chcieť použiť intervalový strom pre postupnosť s iným počtom prvkov, môžeme ju doplniť nulami na najbližšiu väčšiu mocninu dvojky. Postupnosť tým predĺžime nanajvýš dvakrát, takže asymptotickú časovú ani pamäťovú zložitosť nám to nezhorší.

Ako napovedá názov, intervalový strom má štruktúru stromu, konkrétne úplného binárneho stromu.

Úplný binárny strom je zakorenený strom, v ktorom majú všetky listy rovnakú hĺbku a všetky vrcholy okrem listov majú práve dvoch synov (ľavého a pravého). Ľahko sa presvedčíme, že počet listov binárneho stromu je vždy nejaká mocnina dvojky. My použijeme strom s $n$ listami, v ktorých si budeme pamätať našu postupnosť prvkov $p_0, p_1, \dots, p_{n-1}$, pričom $p_0$ bude v najľavejšom liste, $p_1$ v druhom najľavejšom atď. Keďže náš strom má $n$ listov, jeho hĺbka bude $\lg n$ (kde symbolom $\lg$ označujeme dvojkový logaritmus).

V každom vrchole, ktorý nie je list, si budeme pamätať súčet všetkých listov v jeho podstrome (teda listov, ktoré sú jeho potomkami). V koreni si teda budeme pamätať súčet všetkých $n$ prvkov $p_0 + p_1 + \dots + p_{n-1}$, v ľavom synovi koreňa si budeme pamätať súčet $p_0 + p_1 + \dots + p_{n/2-1}$, v pravom synovi koreňa bude súčet $p_{n/2} + \dots + p_{n-1}$ atď. Môžeme si všimnúť, že v každom vrchole (okrem listov) je vlastne súčet jeho synov. Zároveň platí, že v každom vrchole je súčet všetkých prvkov našej postupnosti s indexami z nejakého intervalu $[x, y)$ (budeme používať polootvorené intervaly, lebo sa tým vyhneme väčšine $\pm$ jednotiek, ktoré by nám znepríjemňovali implementáciu pri uzavretých intervaloch). Preto sa táto štruktúra nazýva intervalový strom.

Náš strom má $n$ vrcholov na spodnom poschodí (listov), na pochodí o 1 vyššie má $n/2$ vrhcolov, na ďalšom poschodí má $n/4$ vrcholov atď. Dokopy má teda

$$n + \frac{n}{2} + \frac{n}{4} + \dots + 2 + 1 = 2n-1$$

vrcholov, čiže jeho pamäťová zložitosť bude $O(n)$.

Na intervalový strom sa môžeme pozerať ako na hierarchiu úradníkov. Každý vrchol je ú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. Ľavý syn sa stará o ľavú polovicu úseku svojho otca a pravý syn o pravú polovicu. Koreň má teda na starosti interval $[0, n)$, jeho synovia majú na starosti $[0, n/2)$ a $[n/2, n)$, $i$-ty list má na starosti iba prvok $p_i$, čo je vlastne interval $[i, i+1)$.