Sumy prefiksowe

Mamy tablicę t długości n (n<=10^6) wypełnioną liczbami całkowitymi . Musimy odpowiedzieć m razy (m<=10^6) na zapytanie: „Ile wynosi suma liczb z przedziału t[a..b]?”. Oczywiście można to zrobić metodą brut-force, czyli dla każdego zapytania liczyć od początku sumę:

9.    std::cout << suma << std::endl; // wypisujemy wynik i przechodzimy do nowej linii

10.}

Złożoność algorytmu realizującego zadanie metodą brut-force to O(n*m), co przy n i m równych nawet milion nie jest zbyt dobrym wynikiem. Jak więc obliczyć to szybciej? Otóż należy wykorzystać sumy prefiksowe.

Co to suma prefiksowa?

Suma prefiksowa jest to suma danej ilości początkowych elementów tablicy. Żeby ją zastosować, potrzebujemy dodatkowej tablicy. Nazwijmy ją sum_pref.

int sum_pref[n+1];

Zauważmy, że nowa tablica jest o jeden element większa od pierwszej. Kolejnym krokiem jest takie wypełnienie tej tablicy, by 

sum_pref[0] = 0;

for(int i=0; i<n; ++i)

sum_pref[i+1] = sum_pref[i] + t[i];  

Jak wykorzystać tą tablicę. Weźmy przykładowe liczby dla n=10:

i	0	1	2	3	4	5	6	7	8	9	10
t[i]	18	11	6	-2	12	-19	-4	-16	8	-17	–
sum_pref[i]	0	18	29	35	33	45	26	22	6	14	-3

oraz przykładowy przedział [2..5]. Zauważmy, że

Uogólniając – dla danego przedziału [a..b] suma liczb w tym przedziale jest równa 

Umiemy odpowiadać na zapytania w czasie stałym, tj. O(1) Zatem, łącznie z wstępnym przetwarzaniem, cały algorytm działa w czasie liniowym O(n+m).

Suma liczb w tablicy dwuwymiarowej

Dana jest tablica dwuwymiarowa tablica t o wymiarach [n x k] (n,k<=10^3) wypełniona liczbami całkowitymi. Musimy odpowiedzieć na m zapytań (m<=10^6) o sumę liczb w prostokącie [a..b] x [c..d].W tym przypadku będzie nam potrzebna tablica dwuwymiarowa na sumy prefiksowe. Wypełniamy tą tabelę w taki sposób, by sum_pref[i+1][j+1] zawierał sumę liczb w prostokącie [0..i] x [0..j] :

Mając tą tabelę wynik można obliczyć w następujący sposób:

Poniższa animacja przedstawia tablicą t wypełnioną losowymi liczbami. Ramką zaznaczono prostokąt [a..b] x [c..d], z którego sumę chcemy obliczyć.

Prostokąt [0..a] x [0..c] został odjęty dwukrotnie, więc musimy go raz dodać, by otrzymać poprawny wynik.

Pozostała ostatnia kwestia – jak efektywnie liczyć wartości tablicy sum_pref? Otóż bardzo podobnie.

Wyjaśnienie ponownie w postaci animacji:

Jesteśmy w stanie odpowiadać na zapytania w czasie O(1)! Jednak wstępne przetwarzanie wymaga O(n*m) operacji, zatem cały algorytm działa w czasie O(n*m).