Tablica prefix sum przechowuje skumulowane sumy, dzięki czemu dowolna range sum można odpowiedzieć w O(1) po O(n) preprocessingu — zamiast O(n) na zapytanie.
Ideę
Niech będzie sumą pierwszych elementów. Wówczas suma to .
Tablica prefix sum przechowuje skumulowane sumy, dzięki czemu dowolna range sum można odpowiedzieć w O(1) po O(n) preprocessingu — zamiast O(n) na zapytanie.
Niech będzie sumą pierwszych elementów. Wówczas suma to .
prefix[i]iarr[l..r]prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, l, r): # inclusive l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
Idealna dla wielu zapytań range-sum na danych statycznych. Warianty: 2D prefix sums dla sum podmacrzy, prefix XOR i difference arrays dla aktualizacji zakresów. Jeśli tablica zmienia się często, użyj zamiast tego drzewa Fenwick/segment. Uważaj na przesunięcie indeksu (rozmiar n+1).
Sumy prefiksowe zamieniają powtarzające się O(n) zapytania na zakresy w O(1) wyszukiwania — ogromna wygrana, gdy zapytania są częste.
Wzorzec wstępnego obliczenia raz i szybkiej odpowiedzi uogólnia się na wiele zadań przetwarzania danych.
To jest podstawowy element programowania konkurencyjnego i powszechny element konstrukcyjny w analityce.