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{-}\text{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 tylko jeden 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 \in \mathbb{N}}\).
\(m\) : liczba sum; \({m \in \mathbb{N}}\).
\(i, j\) : indeksy w tablicy \(T\); \({i, j \in \mathbb{Z}}\).

Wyjście:

\(m\) sum częściowych tablicy \(T\).

Elementy pomocnicze

\(S\) : tablica sum prefiksowych o rozmiarze \({n+1}\).
\(k\) : indeks; \({k \in \mathbb{Z}}\).

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