Ak máme $n$-prvkovú postupnosť čísel $p_1,p_2, \dots, p_n$ uloženú v poli, prefixové súčty tejto postupnosti vieme zrátať v čase $O(n)$.
Postup je nasledovný: začneme s pomocnou premennou, do ktorej uložíme nulu. V tejto premennej si budeme udržiavať hodnotu aktuálneho prefixového súčtu. Potom postupne prechádzame číslami v našej postupnosti. Každé číslo, ktoré prejdeme, pripočítame k pomocnej premennej. Po každom takomto pripočítaní si zapíšeme aktuálnu hodnotu z pomocnej premennej, napríklad do druhého poľa. Takto postupne získame všetky prefixové súčty.
postupnost = [...]
prefixove_sucty = []
aktualny_sucet = 0
for p in postupnost:
aktualny_sucet += p
prefixove_sucty.append(aktualny_sucet)
Dokonca sa dá zaobísť aj bez pomocnej premennej. Každý prefixový súčet je vlastne predošlý prefixový súčet zväčšený o príslušný prvok postupnosti.
S využitím tohto pozorovania môžeme zjednodušiť náš kód na počítanie prefixových súčtov nasledovne:
postupnost = [...]
prefixove_sucty = []
for p in postupnost:
prefixove_sucty.append(prefixove_sucty[-1] + p)