Zovšeobecnenia

Podobná technika ako prefixové sumy sa dá použiť aj pre iné operácie ako sčítanie, napríklad pre násobenie (prefixové súčiny), ak medzi násobenými číslami nie sú nuly. Zamyslite sa, prečo sa nedajú prefixové súčty použiť pre operáciu max(L,R), ktorá by vrátila najväčší prvok na intervale [L,R). Vo všeobecnosti sa dá použiť pre operáciu z akejkoľvek grupy.

Prefixové sumy sa dajú zovšeobecniť aj do dvoch (prípadne viacerých) rozmerov. Toto zovšeobecnenie nám umožní rýchlo počítať súčty čísel v obdĺžnikových častiach dvojrozmerného poľa. Viac o tomto zovšeobecnení si môžete prečítať v pokračovaní tohoto kurzu.

Ak potrebujeme vedieť rýchlo počítať súčty čísel v daných úsekoch poľa, ale pomedzi to chceme vedieť (rýchlo) meniť obsah poľa, prefixové sumy sú neefektívne. Pri každej zmene v poli by sme totiž museli prefixové sumy vypočítať odznova (minimálne od miesta, kde sme pole menili), čo by v priemere trvalo až $O(n)$ času. V takom prípade je lepšie použiť intervalový strom, ktorý umožňuje súčet čísel na danom úseku spočítať v čase $O(\log n)$ a zmeniť číslo v poli tiež v čase $O(\log n)$. Viac o intervalových stromoch sa môžete dočítať v samostatnom kurze.