Prefix Sum

Prefix sum adalah teknik prekomputasi yang mengubah range sum query dari O(n) menjadi O(1). Bayangkan kita sering ditanya: “Berapa jumlah elemen dari indeks l hingga r?” Tanpa prefix sum, setiap pertanyaan butuh loop O(n). Dengan prefix sum, cukup satu pengurangan. Pada Chapter ini kita akan mempelajari dua varian: prefix sum 1D dengan rumus pref[r+1] - pref[l], dan prefix sum 2D untuk submatriks. Teknik ini menjadi dasar untuk topik lanjutan seperti difference array dan sliding window.

Prefix Sum 1D #

Mekanisme: Akumulasi Prefiks #

Diberikan array a[0..n-1], prefix sum didefinisikan sebagai:

text

pref[0] = 0
pref[i] = a[0] + a[1] + ... + a[i-1]    untuk i >= 1

Perhatikan bahwa pref berukuran n + 1 — elemen pertama adalah 0 agar rumus range sum bekerja tanpa kasus khusus.

Setelah pref dibangun, jumlah elemen pada rentang [l, r] (inklusif) dihitung dengan:

text

sum(l, r) = pref[r+1] - pref[l]

Kode: Bangun dan Query #

cpp
#include <iostream>
#include <vector>

class PrefixSum1D {
    std::vector<long long> pref_;
public:
    explicit PrefixSum1D(const std::vector<int>& a) {
        pref_.resize(a.size() + 1, 0);
        for (std::size_t i = 0; i < a.size(); ++i) {
            pref_[i + 1] = pref_[i] + a[i];
        }
    }
    // jumlah a[l..r] inklusif
    long long query(int l, int r) const {
        return pref_[r + 1] - pref_[l];
    }
};

int main() {
    std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    PrefixSum1D ps(a);

    std::cout << "query(0, 7) = " << ps.query(0, 7) << '\n';  // seluruh
    std::cout << "query(2, 4) = " << ps.query(2, 4) << '\n';  // 4+1+5
    std::cout << "query(5, 5) = " << ps.query(5, 5) << '\n';  // satu elemen
    std::cout << "query(0, 2) = " << ps.query(0, 2) << '\n';  // 3+1+4
    return 0;
}

Output yang Dihasilkan:

text
query(0, 7) = 31
query(2, 4) = 10
query(5, 5) = 9
query(0, 2) = 8

Baris pref_.resize(a.size() + 1, 0);: alokasi array berukuran n + 1. Indeks 0 selalu 0 (basis).
Baris pref_[i + 1] = pref_[i] + a[i];: akumulasi — pref_[i+1] adalah jumlah a[0..i]. Kompleksitas build: O(n).
Baris return pref_[r + 1] - pref_[l];: rumus inti prefix sum. pref_[r+1] = jumlah a[0..r]; pref_[l] = jumlah a[0..l-1]. Selisihnya = jumlah a[l..r]. Kompleksitas query: O(1).
Hasil query(2, 4) = 10: a[2] + a[3] + a[4] = 4 + 1 + 5 = 10. Sesuai.

Visualisasi Cara Kerja #

Untuk array a = [3, 1, 4, 1, 5], prefix sum dibangun sebagai:

text
i:       0   1   2   3   4   5
a:       3   1   4   1   5   -
pref:    0   3   4   8   9  14
         ^   ^   ^   ^   ^   ^
         |   |   |   |   |   |
         0  0+3 3+1 4+4 8+1 9+5

Query sum(1, 3) = pref[4] - pref[1] = 9 - 3 = 6 (yaitu 1 + 4 + 1).

Prefix Sum 2D #

Mekanisme: Inklusi-Eksklusi #

Untuk matriks m[i][j], prefix sum 2D didefinisikan sebagai:

text

pref[i][j] = jumlah semua elemen m[x][y] dengan 0 <= x < i dan 0 <= y < j

Sama seperti 1D, pref berukuran (R+1) × (C+1). Konstruksi menggunakan rumus inklusi-eksklusi:

text

pref[i][j] = m[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]

Query jumlah submatriks dengan sudut kiri-atas (r1, c1) dan kanan-bawah (r2, c2):

text

sum(r1, c1, r2, c2) = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]

flowchart TD A["Matriks awal\nm[i-1][j-1]"] --> B["pref[i][j] =\nm[i-1][j-1]\n+ pref[i-1][j]\n+ pref[i][j-1]\n- pref[i-1][j-1]"]

Kode: Prefix Sum 2D #

cpp
#include <iostream>
#include <vector>

class PrefixSum2D {
    std::vector<std::vector<long long>> pref_;
public:
    PrefixSum2D(const std::vector<std::vector<int>>& m) {
        int R = static_cast<int>(m.size());
        int C = static_cast<int>(m[0].size());
        pref_.assign(R + 1, std::vector<long long>(C + 1, 0));
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                pref_[i][j] = m[i-1][j-1]
                            + pref_[i-1][j]
                            + pref_[i][j-1]
                            - pref_[i-1][j-1];
            }
        }
    }
    long long query(int r1, int c1, int r2, int c2) const {
        return pref_[r2+1][c2+1]
             - pref_[r1][c2+1]
             - pref_[r2+1][c1]
             + pref_[r1][c1];
    }
};

int main() {
    std::vector<std::vector<int>> m = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    PrefixSum2D ps(m);

    std::cout << "total seluruh = " << ps.query(0, 0, 2, 2) << '\n';
    std::cout << "submatriks (0,0)-(1,1) = " << ps.query(0, 0, 1, 1) << '\n';
    std::cout << "submatriks (1,1)-(2,2) = " << ps.query(1, 1, 2, 2) << '\n';
    std::cout << "sel (2,2) = " << ps.query(2, 2, 2, 2) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
total seluruh = 45
submatriks (0,0)-(1,1) = 12
submatriks (1,1)-(2,2) = 28
sel (2,2) = 9

Baris pref_.assign(R + 1, std::vector<long long>(C + 1, 0));: matriks prefix berukuran (R+1) × (C+1). Baris-0 dan kolom-0 diisi 0 sebagai basis.
Baris pref_[i][j] = m[i-1][j-1] + pref_[i-1][j] + pref_[i][j-1] - pref_[i-1][j-1];: rumus inklusi-eksklusi. pref[i-1][j-1] dikurangi karena ditambah dua kali (sekali di pref[i-1][j], sekali di pref[i][j-1]).
Baris pref_[r2+1][c2+1] - pref_[r1][c2+1] - pref_[r2+1][c1] + pref_[r1][c1];: rumus query. pref[r1][c1] ditambah kembali karena dikurangi dua kali.
Verifikasi submatriks (0,0)-(1,1) = 12: 1 + 2 + 4 + 5 = 12. Sesuai.

Kompleksitas dan Kasus Penggunaan #

Tabel ringkasan kompleksitas prefix sum:

Operasi	1D	2D
Build	O(n)	O(R × C)
Memori	O(n)	O(R × C)
Range sum query	O(1)	O(1)
Update elemen tunggal	O(n) rebuild	O(R × C) rebuild

Prefix sum cocok untuk skenario read-heavy: banyak query, sedikit update. Bila sering update, gunakan struktur data lain seperti Fenwick tree (BIT) yang mendukung update dan query keduanya O(log n).

Aplikasi Lanjutan #

Subarray dengan Jumlah Tertentu #

Bila kita ingin tahu apakah ada subarray berjumlah K, kita dapat memanfaatkan prefix sum dengan hash map:

cpp
#include <iostream>
#include <vector>
#include <unordered_set>

bool ada_subarray_jumlah_K(const std::vector<int>& a, int K) {
    std::unordered_set<long long> seen;
    seen.insert(0);     // basis: prefix awal
    long long pref = 0;
    for (int x : a) {
        pref += x;
        if (seen.count(pref - K)) return true;
        seen.insert(pref);
    }
    return false;
}

int main() {
    std::vector<int> a = {1, 4, 20, 3, 10, 5};
    std::cout << "ada subarray jumlah 33? "
              << (ada_subarray_jumlah_K(a, 33) ? "YA" : "TIDAK") << '\n';
    std::cout << "ada subarray jumlah 100? "
              << (ada_subarray_jumlah_K(a, 100) ? "YA" : "TIDAK") << '\n';
    return 0;
}

Output yang Dihasilkan:

text

ada subarray jumlah 33? YA
ada subarray jumlah 100? TIDAK

Baris seen.insert(0);: basis — prefix awal 0 (sebelum ada elemen). Memungkinkan deteksi subarray yang dimulai dari indeks 0.
Baris pref += x;: akumulasi prefix secara online. Setiap iterasi menambah elemen baru.
Baris if (seen.count(pref - K)) return true;: bila ada prefix sebelumnya yang sama dengan pref - K, maka subarray dari posisi setelah prefix tersebut hingga posisi saat ini berjumlah tepat K.
Hasil 33? YA: subarray {20, 3, 10} = 33. Sesuai.

Ringkasan #

Prefix sum 1D: bangun pref[i+1] = pref[i] + a[i], query sum(l, r) = pref[r+1] - pref[l].
Prefix sum 2D: gunakan rumus inklusi-eksklusi untuk build dan query. Ukuran array pref adalah (R+1) × (C+1).
Build O(n) atau O(R × C), query O(1). Memori sebanding jumlah elemen.
Gunakan long long untuk akumulasi — overflow adalah bug paling umum pada prefix sum.
Untuk skenario dengan update, gunakan Fenwick tree (BIT) yang mendukung update + query keduanya O(log n).