std::partial_sum în C++

OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);
OutputIt inclusive_scan(InputIt first, InputIt last, OutputIt d_first);  // C++17

Ce face std::partial_sum

std::partial_sum scrie la destinație a0, a0 + a1, a0 + a1 + a2 și așa mai departe. Destinația poate fi chiar sursa. Cu un al patrulea argument poți folosi altă operație, de exemplu produsul sau maximul.

std::inclusive_scan (C++17) dă același rezultat, dar, ca std::reduce, nu garantează ordinea operațiilor și poate fi paralelizat. Varianta std::exclusive_scan nu include elementul curent în suma lui.

Sumele parțiale permit răspunsul imediat la întrebări de tipul „cât este suma de la poziția i la j?”: s[j] - s[i - 1].

Parametri

Parametru	Descriere
first, last	Intervalul sursă.
d_first	Destinația.
op	Opțional. Operația folosită în locul adunării.

Ce returnează

Iterator după ultimul element scris.

Exemple

Exemplul 1: Sold cumulat pe luni

#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> economii{500, 300, -200, 450, 100};
    std::vector<int> sold(economii.size());

    std::partial_sum(economii.begin(), economii.end(), sold.begin());
    std::println("Economii: {}", economii);
    std::println("Sold:     {}", sold);
}

Rezultat

Economii: [500, 300, -200, 450, 100]
Sold:     [500, 800, 600, 1050, 1150]

Exemplul 2: inclusive_scan și maximul de până acum

#include <algorithm>
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2};
    std::vector<int> sume(v.size());
    std::vector<int> record(v.size());

    std::inclusive_scan(v.begin(), v.end(), sume.begin());
    std::partial_sum(v.begin(), v.end(), record.begin(), [](int a, int b) { return std::max(a, b); });

    std::println("Sume:   {}", sume);
    std::println("Record: {}", record);
}

Rezultat

Sume:   [3, 4, 8, 9, 14, 23, 25]
Record: [3, 3, 4, 4, 5, 9, 9]

Exemplul 3: Suma pe un interval în timp constant

#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> vizitatori{120, 80, 95, 200, 150, 60, 90};
    std::vector<int> s(vizitatori.size());
    std::partial_sum(vizitatori.begin(), vizitatori.end(), s.begin());

    // vizitatori din zilele 3..5 (indici 2..4)
    std::println("Zilele 3-5: {}", s[4] - s[1]);
}

Rezultat

Zilele 3-5: 445

Greșeli frecvente

• Sumele cumulate depășesc limita lui int pe date mari. Folosește un vector destinație de long long.

Comenzi înrudite

• std::adjacent_difference: Calculează diferențele dintre fiecare element și cel dinaintea lui; primul element este copiat neschimbat.
• std::accumulate: Adună toate elementele unui interval pornind de la o valoare inițială (sau le combină cu o operație dată).
• std::reduce: Ca accumulate, dar fără ordine fixă a operațiilor, ceea ce permite calcul în paralel.