Sumy prefiksowe

Dzisiaj dowiemy się, jak szybko odpowiadać na wiele zapytań o sumy fragmentów tablic.

Problem

Mamy tablicę t długości n () wypełnioną liczbami całkowitymi . Musimy odpowiedzieć m razy () 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ę:

1. int t[n]; // nasza tablica
2. // wczytywanie danych pominięte
3. int a,b; // przedział
4. for (int i=0; i<m; ++i) {
5.  std::cin >> a >> b; // wczytujemy dane
6.  int suma = 0;
7.  for (int j=a; j<=b; ++j) // liczymy sumę
8.  suma += t[a];
9.  std::cout << suma << std::endl; // wypisujemy wynik i przechodzimy do nowej linii
10.}

Jednak złożoność takiego algorytmu to , 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.

1. 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

 
1. sum_pref[0] = 0;
2. for(int i=0; i<n; ++i)
3.  sum_pref[i+1] = sum_pref[i] + t[i];

Jak to działa?

Teraz słówko o tym, jak w zasadzie mamy wykorzystać tą tablicę. Weźmy przykładowe liczby dla :

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 suma liczb w tym przedziale jest równa . Czyż to nie wspaniale? Umiemy odpowiadać na zapytania w czasie stałym, tj. ! Zatem, łącznie z wstępnym przetwarzaniem, cały algorytm działa w czasie liniowym .

1. int t[n];
2. // wczytywanie danych pominięte
3. int sum_pref[n+1];
4. // liczymy tablicę sum_pref
5. sum_pref[0] = 0;
6. for(int i=0; i<n; ++i)
7.  sum_pref[i+1] = sum_pref[i]+t[i]; 
8. int a,b;
9. // odpowiadamy na zapytania
10. for (int i=0; i<m; ++i) {
11.  std::cin >> a >> b; // wczytujemy przedział
12.  int suma = sum_pref[b+1]-sum_pref[a]; // liczymy wynik
13.  std::cout << suma << std::endl; // wypisujemy wynik na ekran i przechodzimy do nowej linii
14.}
 

Suma liczb w tablicy dwuwymiarowej

Wiemy już, jak efektywnie liczyć sumę liczb w jednowymiarowej tablicy. Teraz przyjrzyjmy się podobnemu problemowi:

Dana jest tablica dwuwymiarowa tablica t o wymiarach [n x k] () wypełniona liczbami całkowitymi. Musimy odpowiedzieć na m zapytań () o sumę liczb w prostokącie [a..b] x [c..d]. Jak można się domyślać, 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:

No ale zaraz, zaraz. Skąd się wziął ten wzór? Spójrzmy na poniższą animację przedstawiającą 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:

Dla dopełnienia wiedzy załączam jeszcze sam kod algorytmu w C++.

1. int t[n][k]; 
2. // wczytywanie danych pominięte
3. int sum_pref[n+1][k+1];
4. // zerujemy pierwszy wiersz i kolumnę tabeli
5. for(int a=0;a<=n;++a)
6. sum_pref[a][0] = 0;
7. for(int b=0;b<=k;++b)
8.  sum_pref[0][b] = 0;
9. // liczymy tablicę sum_pref
10. for(int a=0;a<n;++a)
11.  for(int b=0;b<k;++b)
12.  sum_pref[a+1][b+1] = sum_pref[a][b+1] + sum_pref[a+1][b] - sum_pref[a][b] + t[a][b];
13. // odpowiadamy na m zapytań
14. for(int i=0; i<m; ++i) {
15.  int a,b,c,d;
16.  std::cin >> a >> b >> c >> d; // wczytujemy współrzędne prostokąta
17.  int wynik = sum_pref[b+1][d+1] - sum_pref[a][d+1] - sum_pref[b+1][c] + sum_pref[a][c]; // obliczamy wynik
18.  std::cout << wynik << std::endl; // wypisujemy na ekran wynik i przechodzimy do nowej linii
19. }

Znów jesteśmy w stanie odpowiadać na zapytania w czasie ! Jednak wstępne przetwarzanie wymaga operacji, zatem cały algorytm działa w czasie .

Praktyka

Skoro znamy już całą teorię, możemy ją wykorzystać w zadaniach z poprzednich edycji Olimpiady Informatycznej. Zachęcam każdego do samodzielnego rozwiązania w wolnym czasie zadania Mapa Gęstości (VIII Olimpiada Informatyczna, 1 etap) i sprawdzenia rozwiązania w serwisie MAIN ( http://main.edu.pl ).