sumy prefiksowe

Typ 1

Do czego służą?

Sumy prefiksowe(typ 1) służą do szybkiego odpowiadania na zapytania dotyczące np. sumy na danym przedziale danego ciągu. Obsługują tylko ten jeden typ zapytań, ale odpowiadają w złożoności O(1). Wymagają jednak preprocessingu - musimy sobie coś przygotować... Robimy to przed zapytaniami, w czasie liniowym. UWAGA sumy prefiksowe tego typu obsługują tylko zapytania o dany przedział, nie obsługują zamiany wartości w jakimś punkcie.

Algorytm

Stwórzmy tablicę, gdzie będziemy trzymać w i-tej komórce sumę na przedziale od 1 do i. Wtedy będziemy mogli szybko odpowiedzieć na zapytanie o przedział a-b po prostu zwracając sum_pref[b] - sum_pref[a - 1]. Czemu właśnie tak? Zauważmy, że w komórce j-tej mamy sumę od 1 do b. Mamy więc za dużo o przedział od 1 do a - 1. Tak więc od sum_pref[b] odejmujemy sum_pref[a - 1]. Funkcja wypel zajmie się wypełnieniem tablicy sum prefiksowych. Funkcja odp natomiast będzie nam odpowiadać na zapytania o przedział od a do b.

Przykład

Przeanalizujmy przykładowe dane dla naszych sum prefiksowych. Załóżmy, że mamy taki ciąg:
1 5 3 6 7 3 10
Odpowiedzmy na takie zapytania:
1 3
2 4
4 6
4 7
5 5
tablica sum prefiksowych będzie wyglądać tak:
0 1 2 34567 (indeksy)
0 1 6 9 15 22 25 35
A teraz odpowiedzi na zapytania:
1 3 -> 9 - 0 = 9
2 4 -> 15 - 1 = 14
4 6 -> 25 - 9 = 16
4 7 -> 35 - 9 = 26
5 5 -> 22 - 15 = 7

Implementacja i złożoność

implementacja w c++:

const int MAXI = 1000000 + 7;
long long sumy_prefiksowe[MAXI];

void wypel(int n){
for(int i = 1; i <=n ; i++){
sumy_prefiksowe[i] += sumy_prefiksowe[i - 1];
}
}

int odp(int a, int b){
return sumy_prefiksowe[b] - sumy_prefiksowe[a - 1];
}

implementacja w python:

maxi = 1000007
sum_pref = [0 for i in range(maxi)]
def wypel(n):
for i in range(1, n + 1):
sum_pref[i] += sum_pref[i - 1]
def odp(a, b):
return sum_pref[b] - sum_pref[a - 1]

złożoność:

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

Zadania

Typ 2

Do czego służą?

Sumy prefiksowe(typ 2) służą do szybkiego dodawania liczby na jakimś przedziale i na koniec odczytywania z punktów jaka tam jest suma. Operacje te nie mogą być wymieszane!

Algorytm

Dla każdej operacji dodania na przedziale od a do b wartości c, dodajemy w tablicy sum c w indeksie a i odejmujemy c w indeksie b + 1. Na koniec raz przesumuwujemy wartości i wpisujemy je do tablicy wynikowej(tam gdzie trzymamy wyniki dla danego punktu). Wartości w danym punkcie a to jest wartość o indeksie a w tej tablicy. Jak zliczamy? Tak samo jak liczymy sumy prefiksowe pierszego typu 🙂. Czemu właśnie w taki sposób dodajemy? Zauważmy, że przy zliczaniu takim jak sumy prefiksowe, coś dodane w indeksie a będzie dodane też to wszystkich późniejszych indeksów. Ale jeśli odejmiemy w pierwszym indeksie, który nie należy do naszego przedziału (czyli b + 1), to dodamy tylko na przedziale - odjęcie wartości odejmnie od wszystkich późniejszych.

Przykład

Zasymulujmy sumy prefiksowe na przykładzie. Weźmy takie operacje dodawania(początek przedziału, koniec przedziału, wartość):
1 3 1
2 4 2
5 5 3
3 4 4
2 5 5
1 4 6
I wypiszmy końcowe wartości w każdym z punktów. Tak będzie wyglądać nasza tablica sum po każdej operacji:
1 2 3 4 5 6(indeksy)
0 0 0 0 0 0(tak wygląda przed wszystkimi operacjami)
1 0 0 -1 0 0
1 2 0 -1 -2 0
1 2 0 -1 1 -3
1 2 4 -1 -3 -3
1 5 4 -1 -3 -8
7 5 4 -1 -9 -8
Tablica wynikowa:
12345 (indeksy)
7 14 18 17 8

Implentacja i złożoność

implementacja w c++:

const int MAXI = 1e6 + 7;
long long sumy[MAXI];
long long w_punkt_koniec[MAXI];

void wypel(int a, int b, int c){
sumy[a] += c;
sumy[b + 1] -= c;
}

void odp(int n){
int lic = 0;
for(int i = 1; i <= n; i++){
lic += sumy[i];
w_punkt_koniec[i] = lic;
}
}

implementacja w python:

sumy = [0 for i in range(1000007)]
w_punkt_koniec = [0 for i in range(1000007)]

def wypel(a, b, c):
sumy[a] += c
sumy[b + 1] -= c

def odp(n):
lic = 0
for i in range(1, n + 1):
lic += sumy[i]
w_punkt_koniec[i] = lic

złożoność:

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

Zadania

Jakie typy operacji pasują do sum prefiksowych?

suma
różnica
iloczyn
xor