Prefix sum 1D sudah dibahas di Chapter Prefix Sum di Section Array . Pada Chapter ini kita akan memperluas ke dua aplikasi yang sering muncul di soal kompetisi: prefix sum 2D (jumlah sub-persegi pada matriks) dan range update dengan difference array (batch update rentang O(1) per update, kemudian rekonstruksi O(n)). Pemahaman kedua varian ini membuka pintu ke teknik seperti 2D binary indexed tree dan offline range update.

Recap: Prefix Sum 1D #

Diberikan array a[0..n-1], prefix sum P[i] = a[0] + a[1] + ... + a[i-1], dengan P[0] = 0. Jumlah subarray a[l..r] = P[r+1] - P[l]. Konstruksi O(n), query O(1). Lihat Chapter sebelumnya untuk kode lengkap.

Prefix Sum 2D: Jumlah Sub-Persegi #

Aturan #

Diberikan matriks M berukuran n × m, jawab q query: “Berapa jumlah elemen pada sub-persegi dengan sudut kiri-atas (r1, c1) dan kanan-bawah (r2, c2)?”. Solusi naif: O(q · n · m). Dengan prefix 2D: O(n·m) precompute + O(1) per query.

Mekanisme: Inklusi-Eksklusi #

Definisikan P[i][j] = jumlah elemen M[0..i-1][0..j-1] (sub-persegi dari sudut kiri-atas matriks). Recurrences:

text 
P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Untuk query jumlah sub-persegi (r1..r2, c1..c2) (inclusive, indeks 0-based):

text 
sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Tanda - P[r1][c1] (sudut kiri-atas) ditambah kembali karena dikurangi dua kali.

Kode: Prefix Sum 2D #

cpp 
#include <iostream>
#include <vector>

class PrefixSum2D {
public:
    PrefixSum2D(const std::vector<std::vector<int>>& M) {
        int n = static_cast<int>(M.size());
        int m = static_cast<int>(M[0].size());
        P.assign(n + 1, std::vector<long long>(m + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                P[i][j] = M[i-1][j-1]
                          + P[i-1][j]
                          + P[i][j-1]
                          - P[i-1][j-1];
            }
        }
    }

    long long query(int r1, int c1, int r2, int c2) const {
        // inclusive, 0-based
        return P[r2+1][c2+1]
             - P[r1][c2+1]
             - P[r2+1][c1]
             + P[r1][c1];
    }

private:
    std::vector<std::vector<long long>> P;
};

int main() {
    std::vector<std::vector<int>> M = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    PrefixSum2D ps(M);
    std::cout << "sum(0,0,1,1) = " << ps.query(0, 0, 1, 1) << '\n';
    std::cout << "sum(1,2,2,3) = " << ps.query(1, 2, 2, 3) << '\n';
    std::cout << "sum(0,0,2,3) = " << ps.query(0, 0, 2, 3) << '\n';
    std::cout << "sum(1,1,1,1) = " << ps.query(1, 1, 1, 1) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
sum(0,0,1,1) = 14
sum(1,2,2,3) = 38
sum(0,0,2,3) = 78
sum(1,1,1,1) = 6
  1. Baris P.assign(n + 1, std::vector<long long>(m + 1, 0));: alokasi matriks (n+1) × (m+1). Baris/kolom indeks 0 berisi 0 (sentinel) untuk menyederhanakan formula inklusi-eksklusi.
  2. Baris P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];: recurrences inklusi-eksklusi. M[i-1][j-1] ditambah, dua sub-persegi tetangga ditambah, dan sudut yang dihitung dobel dikurangi.
  3. Baris return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];: query O(1). Sub-persegi kiri-atas (r1, c1) sampai kanan-bawah (r2, c2).
  4. Hasil sum(0,0,1,1) = 14: sub-persegi {1,2,5,6} = 14. Sesuai.
  5. Hasil sum(0,0,2,3) = 78: seluruh matriks 3×4. Total 1+2+…+12 = 78. Sesuai.
  6. Hasil sum(1,1,1,1) = 6: elemen tunggal M[1][1] = 6. Sesuai.

Range Update dengan Difference Array #

Aturan #

Diberikan array a berukuran n awalnya 0, lalu q operasi: “tambah v ke setiap elemen a[l..r]”. Setelah semua operasi, cetak array akhir. Solusi naif: O(q·n) (loop rentang per update). Dengan difference array d[]: O(q + n).

Mekanisme: Difference Array #

Definisikan d[i] = a[i] - a[i-1] (dengan a[-1] = 0). Update “tambah v ke a[l..r]” setara dengan:

  • d[l] += v — semua elemen dari indeks l ke atas bertambah v.
  • d[r+1] -= v — batasi efek hanya sampai indeks r.

Setelah semua update, rekonstruksi a[i] = a[i-1] + d[i] dengan a[0] = d[0]. Total O(q + n).

Kode: Difference Array #

cpp 
#include <iostream>
#include <vector>

class DiffArray {
public:
    explicit DiffArray(int n) : d(n + 1, 0) {}

    void add(int l, int r, long long v) {
        d[l] += v;
        d[r + 1] -= v;
    }

    std::vector<long long> finalize() const {
        std::vector<long long> a(d.size() - 1);
        long long cur = 0;
        for (size_t i = 0; i < a.size(); ++i) {
            cur += d[i];
            a[i] = cur;
        }
        return a;
    }

private:
    std::vector<long long> d;
};

int main() {
    DiffArray da(8);
    da.add(0, 4, 3);   // +3 ke a[0..4]
    da.add(2, 5, -2);  // -2 ke a[2..5]
    da.add(3, 7, 5);   // +5 ke a[3..7]
    da.add(1, 6, 1);   // +1 ke a[1..6]
    auto a = da.finalize();
    std::cout << "array akhir: ";
    for (long long x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
array akhir: 3 4 2 7 7 4 6 5
  1. Baris explicit DiffArray(int n) : d(n + 1, 0) {}: alokasi n+1 agar d[r+1] aman saat r = n-1.
  2. Baris d[l] += v;: tandai awal efek update.
  3. Baris d[r+1] -= v;: tandai akhir efek update (batasi agar tidak menjalar ke kanan).
  4. Baris cur += d[i]; a[i] = cur;: rekonstruksi array dengan akumulasi prefix. cur adalah nilai a[i] setelah semua update.
  5. Hasil idx 0 = 3: hanya update [0,4]+3 yang mencakup indeks 0 → 3.
  6. Hasil idx 3 = 7: empat update mencakup indeks 3 — [0,4]+3, [2,5]-2, [3,7]+5, [1,6]+1 → 3 - 2 + 5 + 1 = 7. Sesuai.

Aplikasi Lanjutan: Imbalance 2D #

Kombinasi prefix sum 2D + difference array memungkinkan range update 2D — update kotak (r1,c1)→(r2,c2) dengan nilai v dalam O(1), kemudian rekonstruksi matriks O(n·m). Formula perluasan dari 1D ke 2D:

text 
d[r1][c1] += v
d[r1][c2+1] -= v
d[r2+1][c1] -= v
d[r2+1][c2+1] += v

Setelah semua update, lakukan prefix sum 2D dua tahap: akumulasi kolom, lalu akumulasi baris (atau gunakan formula P[i][j] = d[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]).

Ringkasan #

  • Prefix sum 1D: P[i] = a[0] + ... + a[i-1]. Query a[l..r] = P[r+1] - P[l]. O(n) precompute, O(1) query.
  • Prefix sum 2D: matriks P[i][j] simpan jumlah sub-persegi dari (0,0) ke (i-1,j-1). Query O(1) dengan inklusi-eksklusi.
  • Difference array: update rentang O(1) via d[l] += v dan d[r+1] -= v. Rekonstruksi O(n) via prefix sum.
  • Gabungan keduanya membuka pintu ke offline range update 2D dan banyak soal “imbalance” kompetisi.