Algoritmi → Napredne tehnike → Prefiksne sume i niz razlika

Prefiksne sume i niz razlika

Prefiksne sume

Za niz a[1..n] definišemo p[0] = 0 i p[i] = a[1] + a[2] + … + a[i]. Računa se jednim prolazom: p[i] = p[i − 1] + a[i]. Zbir dela od l do r je tada

a[l] + … + a[r] = p[r] − p[l − 1]

Na primer, zbir a[2..5] = 1 + 4 + 1 + 5 = 11 = p[5] − p[1] = 14 − 3.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> p(n + 1, 0);          // p[0] = 0
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        p[i] = p[i - 1] + x;                // zbir prvih i elemenata
    }
    while (q--) {
        int l, r;
        cin >> l >> r;                      // pozicije od 1
        cout << p[r] - p[l - 1] << "\n";    // zbir a[l..r] u O(1)
    }
    return 0;
}

Priprema traje O(n), a svaki upit O(1) – ukupno O(n + q) umesto O(n · q). Indeksiranje od 1 i p[0] = 0 uklanjaju poseban slučaj za l = 1.

Niz razlika: dodavanje na intervalu

Obrnut problem: mnogo puta treba dodati vrednost v svim elementima od l do r, a niz se ispisuje tek na kraju. Umesto da menjamo sve elemente, u pomoćni niz d upišemo d[l] += v i d[r + 1] −= v. Na kraju prefiksne sume niza d daju koliko je dodato svakom elementu.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 2, 0), d(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;                      // od l počinje dodavanje
        d[r + 1] -= v;                  // posle r prestaje
    }
    long long dodato = 0;
    for (int i = 1; i <= n; i++) {
        dodato += d[i];                 // prefiksna suma niza razlika
        cout << a[i] + dodato << " ";
    }
    cout << endl;
    return 0;
}

Prefiksne sume u matrici

Za matricu a[1..n][1..m] neka je p[i][j] zbir pravougaonika od (1, 1) do (i, j):

p[i][j] = a[i][j] + p[i−1][j] + p[i][j−1] − p[i−1][j−1]

(gornji i levi deo smo sabrali, a njihov zajednički deo je ubrojan dva puta, pa ga oduzimamo). Zbir pravougaonika od (x1, y1) do (x2, y2):

p[x2][y2] − p[x1−1][y2] − p[x2][y1−1] + p[x1−1][y1−1]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> p(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            long long x;
            cin >> x;
            p[i][j] = x + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje