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.

n               # pocet prvkov postupnosti
p = [0] * n     # vstupne pole, p[0] je prvy prvok postupnosti.
s = [0] * (n+1) # sem chceme ulozit prefixove sucty, s[0] bude nulta prefixova suma.

s[0] = 0;
pom = 0;
for i in range(n):
    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}$.

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:

n               # pocet prvkov postupnosti
p = [0] * n     # vstupne pole, p[0] je prvy prvok postupnosti.
s = [0] * (n+1) # sem chceme ulozit prefixove sucty, s[0] bude nulta prefixova suma.

s[0] = 0;
for i in range(n):
    s[i+1] = s[i] + p[i]