Sumy sufiksowe i prefiksowe

Sumy prefiksowe:

Mamy pewien dowolny ciąg a np. (1,5,3,6,7).

Sumy prefiksowe polegają na stworzeniu nowego ciągu, nazwijmy go b składającego się z sum kolejnych liczb ciągu a, czyli do poprzedniego elementu nowego ciągu b dodajemy kolejny element naszego podstawowego ciągu a.

Indeksy	0	1	2	3	4
Ciąg "a"	1	5	3	6	7
Ciąg "b"	1 b0=a0=1	6 b1=b0+a1= =1+5	9 b2=b1+a2= =6+3	15 b3=b2+a3= =9+6	22 b4=b3+a4= =15+7

Możemy więc zauważyć pewną zależność:

Każdy kolejny wyraz nowego ciągu b po odjęciu poprzedniego daje nam element ciągu a:

Np. b4-b3=a4 22-15=7

b2-b1=a2 9-6=3

Tę własność wykorzystamy w naszym algorytmie. Dzięki sumom prefiksowym możemy w łatwy sposób podać sumę liczb w danym przedziale.

Jeśli chcielibyśmy dla naszego wcześniejszego przykładu policzyć sumę elementów dla przedziału otwartego (1,4) – czyli sumę elementów 2 i 3, to zamiast dodawać każdy kolejny element wystarczy, że od elementu b4 odejmiemy b0, czyli:

b4 – b0 = 15 – 1

w ten sposób przy dużych przedziałach znacznie zmniejsza się liczba operacji, które należy wykonać, a nasz program działa sprawniej.

Napiszmy algorytm, który dla ciągu „a” wypisze jego ciąg „b” z sumami prefiksowymi:

#include <iostream>
using namespace std;
int main()
{
    int n;  //deklarujemy zmienną n, która powie nam o ilości liczb w 
			//naszym ciągu oraz dwie tablicę – „a”, do której 
    cin>>n;	// będziemy wczytywać nasz początkowy ciąg oraz „b” na sumy 	
			//prefiksowe,
    int a[n],b[n]={0};	//Wypełniamy je zerami. 
    for(int i=0;i<n;i++) 
    {
	    cin>>a[i];		//wczytujemy dane do tablicy (ciągu) „a”
    }
    b[0] = a[0];		//Pierwsze dwa elementy ciągów są równe
    for(int i=1;i<n;i++)
    {
      b[i]=a[i]+b[i-1];		
      //wypełniamy tablicę „b” zgodnie z wcześniej opisaną 		
      //zależnością (do poprzedniego elementu tablicy b dodajemy 	
      //element tablicy a
    }
    for(int i=0;i<n;i++)
    {
	    cout<<b[i]<<"\n";  //wypisujemy liczby z tablicy „b”
    }
    return 0;
}

Nasz program składa się z jednej pętli obliczającej sumę prefiksową złożoność obliczeniowa jest liniowa O(n), a każde zapytanie o sumę będziemy mogli rozwiązywać w złożoności stałej O(1).

ZADANIE: zmodyfikuj powyższy program tak, aby wypisywał sumy przedziałów podanych przez użytkownika.

Sumy sufiksowe:

Mamy pewien dowolny ciąg a np. (11,35,8,16,17).

Sumy sufiksowe polegają na stworzeniu nowego ciągu, b składającego się z sum kolejnych liczb ciągu a. Pierwszy element ciągu b jest sumą wszystkich liczb z ciągu a, drugi sumą wszystkich liczb ciągu a poza ostatnią, trzeci wszystkich poza dwiema ostatnimi itd.

Indeksy	0	1	2	3	4
Ciąg "a"	11	35	8	16	17
Ciąg "b"	87 b0=a0+a1+a2+a3+a4=11+35+8+16+17	76 b1=a1+a2+a3+a4=35+8+16+17	41 b2=a2+a3+a4=8+16+17	33 b3=a3+a4= =16+17	17 b4=a4=17

Możemy więc zauważyć pewną zależność:

Każdy wyraz nowego ciągu b po odjęciu od niego następnego daje nam element ciągu a:

Np. b3-b4=a3 33-17=16

b1-b2=a1 76-41=35

Tę własność wykorzystamy w naszym algorytmie.

Napiszmy algorytm, który dla ciągu „a” wypisze jego ciąg „b” z sumami sufiksowymi:

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],b[n];  //deklarujemy zmienną n oraz dwie tablicę – „a”, do której 
                    //będziemy wczytywać liczby i „b” na sumy sufiksowe. 
    for(int i=0;i<n;i++)
    {
	    cin>>a[i];	//wczytujemy liczby do tablicy „a”.
    }
    b[n-1]=a[n-1]; 	//ostatni element ciągu "b" jest równy ostatniemu 
                    //elementowi "a” 
    for(int i=n-2;i>=0;i--)	//wypełniamy tablicę „b” od końca zgodnie z 
                            //wcześniej opisaną zależnością   
    {			    
	    b[i]=b[i+1]+a[i];         
    }                             
    for(int i=0;i<n;i++)
    {
	    cout<<b[i]<<"\n";   //wypisujemy liczby z tablicy „b”. 
    }
    return 0;
}

Program składa się z jednej pętli obliczającej sumę sufiksową, więc złożoność obliczeniowa jest liniowa O(n), a każde zapytanie o sumę będziemy mogli rozwiązywać w złożoności stałej O(1).

ZADANIE: Napisz program, w którym wczytasz ciąg sum sufiksowych dla pewnego ciągu “a” oraz liczbę x. Wypisz element ciągu a o indeksie x.