Algorytmy i Struktury Danych

Pierwszym, narzucającym się rozwiązaniem jest proste policzenie sumy elementów tablicy od T[i] do T[j] i zwrócenie wyniku. Gdyby to był pojedynczy problem, to oczywiście tak należałoby postąpić. Tutaj jednak musimy wyznaczyć m takich sum. Aby nie powtarzać zliczania elementów tablicy, utwórzmy tablicę tzw. sum prefiksowych. Element i-ty tej tablicy jest sumą elementów elementów od T[0] do T[i-1].

Przykład:

Załóżmy, że mamy tablicę T o następującej zawartości:

T	indeks	0	1	2	3	4	5	6	7	8	9
T	zawartość	-5	3	8	12	4	-7	-2	1	0	-6

Wyliczamy dla tej tablicy tablicę sum prefiksowych. Pierwszy element tej tablicy jest zawsze równy 0. Następne elementy powstają przez dodanie do elementu poprzedniego kolejnego elementu z tablicy T. Tablica sum prefiksowych ma o 1 element więcej niż tablica T.

S	indeks	0	1	2	3	4	5	6	7	8	9	10
S	zawartość	0	-5	-2	6	18	22	15	13	14	14	8

Aby teraz otrzymać sumę elementów od T[i] do T[j] wystarczy wykonać odejmowanie: S[j+1]-S[i]. Dlaczego? S[j+1] jest sumą kolejnych elementów od T[0] do T[j]. S[i] jest sumą elementów od T[0] do T[i-1], mamy:

S[j+1]-S[i] =
T[0]+T[1]+…+T[j-1]+T[j]-T[0]-T[1]-…-T[i-2]-T[i-1] =
T[i]+T[i+1]+…+T[j-1]+T[j]

Widzisz zatem, że w sumie pozostają tylko elementy od T[i] do T[j].

Rozwiązanie problemu będzie dwuetapowe. W pierwszym etapie wyliczamy tablicę sum prefiksowych S. W drugim etapie odczytujemy m, po czym m razy odczytujemy indeksy i oraz j. Wyznaczamy sumę od T[i] do T[j] jako różnicę S[j+1]-S[i] i zwracamy wynik. Zaletą tego rozwiązania jest to, że sumy liczymy raz w czasie O(n).

Algorytm liczenia sum częściowych tablicy za pomocą sum prefiksowych

Wejście:

T : tablica z elementami do sumowania.
n : liczba elementów w tablicy T. n ∈ N.
m : liczba sum, m ∈ N.
i, j : indeksy w tablicy T. i, j ∈ C.

Wyjście:

m sum częściowych tablicy T.

Elementy pomocnicze

S : tablica sum prefiksowych o rozmiarze n+1.
k : indeks, k ∈ C.

Lista kroków

K01: S[0] ← 0 ; pierwsza suma równa zero
K02: Dla k = 0, 1, …, n-1:
     wykonuj S[k+1] ← S[k]+T[k] ; suma prefiksowa
K03: Czytaj m ; liczba sum częściowych
K04: Dla k = 1, 2, …, m:
     wykonuj kroki K05…K06
K05:   Czytaj i, j ; odczytujemy indeks początku i końca sumy częściowej
K06:   Pisz S[j+1]-S[i] ; zwracamy sumę częściową od T[i] do T[j]
K07: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy tablicę T o 15 pseudolosowych elementach. Następnie wylicza dla tej tablicy sumy prefiksowe, po czym generuje 10 razy losowe indeksy i oraz j i wypisuje sumy częściowe od T[i] do T[j].

Pascal

// Sumy prefiksowe
// Data: 26.09.2015
// (C)2015 mgr Jerzy Wałaszek
//---------------------------

program project1;

const N = 15; // Liczba elementów
      M = 10; // Liczba sum częściowych

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  T : array [0..N-1] of integer;
  S : array [0..N]   of integer;
  i, j, k, x : integer;
begin
  Randomize; // Inicjujemy generator pseudolosowy
  for k := 0 to N-1 do // Ustawiamy tablicę T
    T[k] := random(N)-random(N);
  S[0] := 0;
  for k := 0 to N-1 do // Wyliczamy sumy prefiksowe
    S[k+1] := S[k]+T[k];
  write('T = '); // Wyświetlamy obie tablice
  for k := 0 to N-1 do write(T[k]:4);
  writeln;
  write ('S = ');
  for k := 0 to N do write(S[k]:4);
  writeln;
  writeln;
  for k := 1 to M do // Wyliczamy sumy częściowe
  begin
    i := random(N); // Losujemy indeksy
    j := random(N);
    if i > j then
    begin
      x := i; i := j; j := x;
    end;
    writeln('Suma od T[', i:2, '] do T[', j:2, '] wynosi ', S[j+1]-S[i]);
  end;
end.

C++

// Sumy prefiksowe
// Data: 26.09.2015
// (C)2015 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 15; // Liczba elementów
const int M = 10; // Liczba sum częściowych

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int T[N], S[N+1], i, j, k;

  srand(time(NULL));
  for(k = 0; k < N; k++) // Ustawiamy tablicę T
    T[k] = (rand() % N)-(rand() % N);
  S[0] = 0;
  for(k = 0; k < N; k++) // Wyliczamy sumy prefiksowe
    S[k+1] = S[k]+T[k];
  cout << "T = "; // Wyświetlamy obie tablice
  for(k = 0; k < N; k++)
    cout << setw(4) << T[k];
  cout << endl << "S = ";
  for(k = 0; k <= N; k++)
    cout << setw(4) << S[k];
  cout << endl << endl;
  for(k = 0; k < M; k++) // Wyliczamy sumy częściowe
  {
    i = rand() % N; // Losujemy indeksy
    j = rand() % N;
    if(i > j) swap(i, j);
    cout << "Suma od T[" << setw(2) << i
         << "] do T[" << setw(2) << j
         << "] wynosi " << S[j+1]-S[i] << endl;
  }
  return 0;
}

Basic

' Sumy prefiksowe
' Data: 26.09.2015
' (C)2015 mgr Jerzy Wałaszek
'---------------------------

const N = 15 ' Liczba elementów
const M = 10 ' Liczba sum częściowych

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer T(0 To N-1)
Dim As Integer S(0 To N)
Dim As Integer i, j, k

Randomize ' Inicjujemy generator pseudolosowy
For k = 0 To N-1 ' Ustawiamy tablicę T
  T(k) = Int(N*(Rnd-Rnd))
Next
S(0) = 0
For k = 0 To N-1 ' Wyliczamy sumy prefiksowe
  S(k+1) = S(k)+T(k)
Next
Print "T = "; ' Wyświetlamy obie tablice
For k = 0 To N-1
  Print Using "####";T(k);
Next
Print
Print "S = ";
For k = 0 To N
  Print Using "####";S(k);
Next
Print
Print
For k = 1 To M ' Wyliczamy sumy częściowe
  i = Int(Rnd*N) ' Losujemy indeksy
  j = Int(Rnd*N) 
  If i > j Then Swap i, j
  Print Using "Suma od T[##] do T[##] wynosi &";i;j;S(j+1)-S(i)
Next
End

Python (dodatek)

# Sumy prefiksowe
# Data:  4.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 15 # Liczba elementów
M = 10 # Liczba sum częściowych

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

t = []
s = [0]*(N+1)
# Ustawiamy tablice T i S
for k in range(N):
    t.append(random.randrange(-N+1, N))
    s[k+1] = s[k]+t[k]
# Wyświetlamy obie tablice
print("T = ", end="")
for k in range(N):
    print("%4d" % t[k], end="")
print()
print("S = ", end="")
for k in range(N+1):
    print("%4d" % s[k], end="")
print()
print()
# Wyliczamy sumy częściowe
for k in range(1, M+1):
    # Losujemy indeksy
    i = random.randrange(N)
    j = random.randrange(N) 
    if i > j:
        i, j = j, i
    print("Suma od T[%2d] do T[%2d] wynosi %d" \
          % (i, j, s[j+1]-s[i]))
print()

Wynik:

T =   -4  -3   5 -12  -7  -7   3  -7  11   1 -10  10   5  -1  -7
S =    0  -4  -7  -2 -14 -21 -28 -25 -32 -21 -20 -30 -20 -15 -16 -23

Suma od T[ 1] do T[ 3] wynosi -10
Suma od T[ 3] do T[ 7] wynosi -30
Suma od T[ 5] do T[11] wynosi 1
Suma od T[ 4] do T[10] wynosi -16
Suma od T[ 6] do T[13] wynosi 12
Suma od T[ 8] do T[13] wynosi 16
Suma od T[ 9] do T[14] wynosi -2
Suma od T[ 0] do T[ 5] wynosi -28
Suma od T[ 2] do T[ 3] wynosi -7
Suma od T[ 5] do T[ 9] wynosi 1

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sumy prefiksowe