Prefixové sumy

Prefixové sumy sú technika, ktorá nám umožňuje efektívne počítať súčty čísel v daných úsekoch poľa. Pre pole dĺžky $n$ potrebujeme predspracovanie v čase $O(n)$, následne vieme v čase $O(1)$ odpovedať otázky typu "Aký je súčet čísel v poli medzi indexmi $L$ a $R$?"

Čo to je?

Majme nejakú postupnosť čísel. Prefixom tejto postupnosti nazývame ľubovoľnú jej súvislú časť, ktorá začína na začiatku postupnosti. Ak by sme napríklad mali postupnosť 1, 7, -3, 12, 18, jej prefixami sú prázdna postupnosť, 1; 1, 7; 1, 7, -3; 1, 7, -3, 12 a 1, 7, -3, 12, 18. Všimnime si, že každá $n$-prvková postupnosť má $n+1$ prefixov (vrátane jej samej a prázdnej postupnosti).

Prefixové sumy (alebo tiež čiastočné súčty, čiastočné sumy alebo prefixové súčty) danej postupnosti sú súčty čísel v jej jednotlivých prefixoch. Prvá prefixová suma je rovná prvému prvku postupnosti, druhá prefixová suma je rovná súčtu prvých dvoch prvkov, tretia je rovná súčtu prvých troch prvkov atď.. Niekedy sa nám hodí definovať aj nultú prefixovú sumu ako nulu (táto nula zodpovedá ,,súčtu'' prázdnej postupnosti). Postupnosť 1, 7, -3, 12, 18 má teda prefixové sumy 0, 1, 8, 5, 17, 35.

Počítanie prefixových súm

Ak máme $n$-prvkovú postupnosť čísel $p_1, p_2 \dots, p_{n}$ uloženú v nejakom poli, prefixové sumy tejto postupnosti vieme zrátať v čase $O(n)$. Urobíme to nasledovne: najprv si do pomocnej premennej dáme nulu. Následne k nej postupne po jednom pričítavame $p_1, p_2, \dots, p_{n}$. Po prvom pričítaní budeme mať v premennej prvú prefixovú sumu, po pričítaní $p_2$ tam bude druhá prefixová suma, po treťom pričítaní tretia atď.. Stačí si teda po každom pričítaní zaznamenať hodnotu pomocnej premennej a dostaneme prefixové sumy.

int n;
int p[n]; //vstupne pole, p[0] je prvy prvok postupnosti.
int s[n+1]; //sem chceme ulozit prefixove sucty, s[0] bude nulta prefixova suma.

s[0] = 0;
int pom = 0;
for(int i=0; i<n; i++) {
    pom += p[i];
    s[i+1] = pom;
}

Dokonca sa dá zaobísť aj bez pomocnej premennej. Označme si $i$-tu prefixovú sumu ako $s_i$. Potom platí $$s_{i+1} = p_1 + p_2 + \dots + p_{i} + p_{i+1} = s_i + p_{i+1} \text{.}$$ Inými slovami, každá prefixová suma (okrem nultej) je vlastne predošlá prefixová suma zväčšená o príslušný prvok postupnosti. S využitím tohto pozorovania môžeme napísať nasledovný kód na počítanie prefixových súm:

int n;
int p[n];
int s[n+1];

s[0] = 0;
for(int i=0; i<n; i++) {
    s[i+1] = s[i] + p[i];
}

Na čo je to dobré?

Keď už máme zrátané prefixové sumy s[0], s[1], ... , s[n] nejakého poľa s prvkami p[0], p[1], ... , p[n-1], vieme rýchlo odpovedať na otázky typu "Aký je súčet prvkov poľa s indexami medzi $L$ a $R$?" Stačí si uvedomiť, že s[R+1] je rovné p[0] + p[1] + ... + p[R] a s[L] je rovné p[0] + p[1] + ... + p[L-1], teda ich rozdiel s[R+1] - s[L] je rovný p[L] + p[L+1] + ... + p[R], čo je presne požadovaný súčet. Ako odpoveď teda môžeme vrátiť číslo s[R+1] - s[L]. Ak v otázke používame polootvorený interval a pýtame sa na súčet čísel s inexami z $[L, R)$ (teda vrátane p[L], ale bez p[R]), výsledok je ešte jednoduchší: s[R] - s[L].

Všimnime si, že tu využívame, že sme si definovali aj nultú prefixovú sumu s[0] (ak sa nás niekto spýta na úsek začínajúci indexom 0).

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. 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 samostatnom článku.

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)$.