sumy prefiksowe 2D

Do czego służą?

Sumy prefiksowe 2D służą do szybkiego odpowiadania na dużo zapytań o np. sumę na danym prostokącie w prostokątnej tablicy Wymagają preprocessingu (musimy przed ich używaniem je przygotować). UWAGA wartości w tablicy nie mogą ulegać zmianie!

Algorytm

W komórce o indeksach i, j trzymamy sumę na prostokącie o lewym górnym rogu w komórce 1, 1; a prawym dolnym rogu w komórce i, j. Czyli wartością dla komórki i, j będzie:
sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + tablica[i][j], gdzie tablica to tablica z wartościami w danej komórce UWAGA w implementacji jako tablicy tablica jest użyta od razu tablica sum. Optymalizuje nam to pamięć. Wracając do wzoru, to czemu taki jest? sum[i - 1][j] i sum[i][j - 1] załatwiają nam sumę z komórki wyżej i z komórki po lewej. To jasne że musimy je dodać. Natomiast sum[i - 1][j - 1] odejmujemy, ponieważ dodaliśmy ją 2 razy: podczas dodawania sum[i - 1][j], sum[i][j - 1]. Możecie sobie tę sytuację narysować, wtedy na pewno lepiej zrozumiecie 🙂. tablica[i][j] dodajemy, ponieważ chcemy mieć sumę łącznie z punktem, który aktualnie rozpatrujemy. To był algorytm na funkcję wypel (wypełniającą nasze sumy). Ale jak odczytywać wyniki z prostokąta o lewym górnym rogu a, b; a prawym dolnym c, d? Bardzo prosto - wykorzystujemy wzorek:
sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1];
Czemu jest taki? Zauważmy, że sum[c][d] to jest cały prostokąt 0, 0; c, d;, czyli mamy trochę za dużo. sum[a-1][d] i sum[c][b - 1] to są indeksy będące na jednej linii z indeksem c, d; ale o 1 poniżej indeksu a, b. Są to więc sumy z prostokątów nie będących w naszym prostokącie, zawierające się w sum[c][d]. Zauważmy jednak, że sum[a - 1][b - 1] odjeliśmy 2 razy, więc dodajemy, żeby było odjęte tylko raz.

Przykład

Zasymuujmy nasze sumy prefiksowe dla takiej tablicy:

1	2
3	1
2	3

I dla takich zapytań (najpierw podaję kolumnę, potem wiersz):
1 1 2 3
2 1 2 2
1 3 2 3
Najpierw obliczamy sumy prefiksowe korzystając z naszego wzoru (jeśli ideksy wyjdą poza tablicę bierzemy 0):

1	3
4	7
6	13

Teraz odpowiadamy na zapytania:
12 - 0 - 0 + 0 = 12
7 - 4 - 0 + 0 = 3
12 - 7 - 0 + 0 = 5

implementacja i złożoność

implementacja w c++:

const int MAXI = 1e3 + 7;
long long sum[MAXI][MAXI];

void wypel(int n, int m){
for(int i = 1; i <=n ; i++){
for(int j = 1; j <=m ; j++){
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
}

int odp(int a, int b, int c, int d){
int wyn = sum[c][d];
wyn -= sum[a - 1][d];
wyn -= sum[c][b - 1];
wyn += sum[a - 1][b - 1];
return wyn;
}

implementacja w python:

maxi = 1007
sum = [[0 for i in range(maxi)] for i in range(maxi)]
def wypel(n, m):
for i in range(1, n + 1):
for j in range(1, m + 1):
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]

def odp(a, b, c, d):
wyn = sum[c][d]
wyn -= sum[a - 1][d]
wyn -= sum[c][b - 1]
wyn += sum[a - 1][b - 1]
return wyn

złożoność:

wypel: O(n*m)
odp: O(1)

Zadania

Uwagi

W sumach prefiktowych 2D trzeba uważać, czy najpierw podają nam kolumnę czy wiersz komórki. Jest to ważne, bo jeśli tego nie sprawdzimy nasze sumy nie zadziałają.

Jakie typy operacji pasują do sum prefiksowych?

suma
różnica
iloczyn
xor