Difference Array

Difference array adalah pasangan natural dari prefix sum. Bayangkan kita perlu menambah v ke seluruh elemen pada rentang [l, r] — operasi yang sering muncul di soal “range update”. Naif: loop dari l ke r, berbiaya O(n) per update. Dengan difference array, cukup dua operasi: d[l] += v dan d[r+1] -= v. Setelah seluruh update selesai, kita materialisasikan array hasil dengan prefix sum. Pada Chapter ini kita akan mempelajari bagaimana difference array membalik arah hubungan dengan prefix sum, beserta varian 2D untuk submatriks.

Konsep Inti #

Mekanisme: Invers dari Prefix Sum #

Diberikan array a, difference array d didefinisikan sebagai:

text

d[0] = a[0]
d[i] = a[i] - a[i-1]     untuk i >= 1

Sifat penting: prefix sum dari d menghasilkan a kembali. Hubungan ini bersifat dua arah:

text

pref_d[i] = d[0] + d[1] + ... + d[i] = a[i]

Operasi Range Update #

Untuk menambah v ke a[l..r] (inklusif), kita cukup:

text

d[l]   += v
d[r+1] -= v

Kenapa? Karena prefix sum mengakumulasi d, d[l] += v akan menambah v ke a[l], a[l+1], ..., a[n-1]. Lalu d[r+1] -= v membatalkan penambahan mulai dari a[r+1] dan seterusnya. Hasil bersih: hanya a[l..r] bertambah v.

flowchart LR A["a: 0 0 0 0 0 0 0"] -->|"update [2..4] += 5"| B["a: 0 0 5 5 5 0 0"] C["d: 0 0 0 0 0 0 0"] -->|"d[2]+=5, d[5]-=5"| D["d: 0 0 5 0 0 -5 0"] D -->|"prefix sum"| B

Kode: Range Update Sederhana #

cpp
#include <iostream>
#include <vector>

class DifferenceArray {
    std::vector<long long> d_;
public:
    explicit DifferenceArray(int n) : d_(n + 1, 0) {}

    // tambah v ke a[l..r] (inklusif)
    void add(int l, int r, long long v) {
        d_[l]     += v;
        d_[r + 1] -= v;
    }

    // materialisasi array hasil
    std::vector<long long> materialize() const {
        std::vector<long long> a(d_.size() - 1);
        long long pref = 0;
        for (std::size_t i = 0; i < a.size(); ++i) {
            pref += d_[i];
            a[i] = pref;
        }
        return a;
    }
};

int main() {
    DifferenceArray da(7);

    da.add(2, 4, 5);   // [0,0,5,5,5,0,0]
    da.add(0, 3, 10);  // [10,10,15,15,5,0,0]
    da.add(5, 6, -3);  // [10,10,15,15,5,-3,-3]

    auto a = da.materialize();
    std::cout << "hasil: ";
    for (long long x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

hasil: 10 10 15 15 5 -3 -3

Baris d_(n + 1, 0): alokasi n + 1 elemen. Slot tambahan di indeks n memungkinkan operasi d[r+1] -= v saat r == n-1 tanpa out-of-bounds.
Baris d_[l] += v; d_[r+1] -= v;: inti teknik — dua operasi O(1) per range update.
Baris pref += d_[i]; a[i] = pref;: materialisasi melalui prefix sum online. Kompleksitas O(n), dilakukan sekali setelah seluruh update.
Verifikasi hasil: array 0 0 0 0 0 0 0 setelah add(2,4,5) menjadi 0 0 5 5 5 0 0. Setelah add(0,3,10) menjadi 10 10 15 15 5 0 0. Setelah add(5,6,-3) menjadi 10 10 15 15 5 -3 -3. Sesuai.

Banyak Range Update Sekaligus #

Skenario: Pewarnaan Interval #

Misalkan kita punya m operasi “warnai rentang [l_i, r_i] dengan warna c_i”, lalu kita ingin tahu warna akhir setiap indeks. Difference array memproses seluruh operasi dalam O(m) + O(n) — jauh lebih cepat daripada O(m × n) naif.

Kode: Range Update Batch #

cpp
#include <iostream>
#include <vector>

int main() {
    int n = 8;

    // Setiap operasi: (l, r, value)
    std::vector<std::tuple<int, int, int>> ops = {
        {0, 4, 1},    // tambah 1 ke indeks 0..4
        {2, 6, 2},    // tambah 2 ke indeks 2..6
        {3, 5, -1},   // kurangi 1 dari indeks 3..5
        {1, 7, 3}     // tambah 3 ke indeks 1..7
    };

    std::vector<long long> d(n + 1, 0);
    for (const auto& [l, r, v] : ops) {
        d[l]     += v;
        d[r + 1] -= v;
    }

    // Materialisasi
    std::vector<long long> a(n);
    long long pref = 0;
    for (int i = 0; i < n; ++i) {
        pref += d[i];
        a[i] = pref;
    }

    std::cout << "array akhir: ";
    for (long long x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

array akhir: 1 4 6 5 5 4 5 3

Baris for (const auto& [l, r, v] : ops): structured binding C++17 — mendekonstruksi tuple (l, r, v) secara langsung. Lebih ringkas daripada std::get<0>(op).
Baris d[l] += v; d[r+1] -= v;: setiap operasi diakumulasi ke array d yang sama. Tidak ada materialisasi per operasi.
Materialisasi sekali di akhir: total kompleksitas O(m + n). Bandingkan dengan naif O(m × n) — untuk m, n = 10^6, perbedaan 10^6 vs 10^12.
Verifikasi indeks 0: operasi yang berdampak — 0,4 → +1, 1,7 → +3. Total +4. Tapi indeks 0 tidak terkena 1,7, sehingga hanya +1. Sesuai output a[0] = 1.

Difference Array 2D #

Mekanisme: Invers Prefix Sum 2D #

Untuk matriks, difference array 2D memungkinkan update submatriks [r1..r2] × [c1..c2] dengan +v dalam O(1). Empat operasi:

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

Materialisasi: prefix sum 2D dari d.

Kode: Submatrix Update #

cpp
#include <iostream>
#include <vector>

int main() {
    int R = 4, C = 4;
    std::vector<std::vector<long long>> d(R + 1, std::vector<long long>(C + 1, 0));

    auto add = [&](int r1, int c1, int r2, int c2, long long v) {
        d[r1][c1]     += v;
        d[r1][c2 + 1] -= v;
        d[r2 + 1][c1] -= v;
        d[r2 + 1][c2 + 1] += v;
    };

    add(0, 0, 2, 2, 5);   // submatriks 3x3 kiri-atas += 5
    add(1, 1, 3, 3, 3);   // submatriks 3x3 tengah-bawah += 3

    // Materialisasi: prefix sum 2D dari d
    std::vector<std::vector<long long>> a(R, std::vector<long long>(C, 0));
    for (int i = 0; i < R; ++i) {
        long long row_pref = 0;
        for (int j = 0; j < C; ++j) {
            // kontribusi dari baris-baris atas
            long long atas = (i > 0) ? a[i-1][j] : 0;
            row_pref += d[i][j];
            a[i][j] = row_pref + atas;
        }
    }

    std::cout << "matriks akhir:\n";
    for (const auto& row : a) {
        for (long long x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
matriks akhir:
5 5 5 0
5 8 8 3
5 8 8 3
0 3 3 3

Lambda add: menangani empat operasi perubahan pada difference array 2D. Setiap submatriks update O(1).
Baris d[r1][c1] += v; d[r1][c2+1] -= v; d[r2+1][c1] -= v; d[r2+1][c2+1] += v;: rumus invers prefix sum 2D. Sudut kanan-bawah +v karena dikurangi dua kali (sekali oleh d[r1][c2+1], sekali oleh d[r2+1][c1]).
Materialisasi: implementasi prefix sum 2D inkremental. row_pref menjumlahkan kontribusi pada baris saat ini; atas menjumlahkan kontribusi kumulatif dari baris-baris di atasnya.
Verifikasi sel [1][1] = 8: terkena kedua update (+5 dari submatriks pertama, +3 dari submatriks kedua). Total +8. Sesuai.

Perbandingan Teknik #

Teknik	Build	Update Range	Query Point	Memori
Naif loop	O(1)	O(n)	O(1)	O(n)
Difference array	O(n)	O(1)	O(n) rebuild	O(n)
Fenwick tree (BIT)	O(n log n)	O(log n)	O(log n)	O(n)
Segment tree	O(n)	O(log n)	O(log n)	O(n)

Difference array unggul saat jumlah update » jumlah materialisasi — misalnya batch processing awal, lalu satu kali read keseluruhan. Bila update dan query tercampur seimbang, BIT atau segment tree lebih cocok.

Ringkasan #

Difference array adalah invers dari prefix sum: d[i] = a[i] - a[i-1].
Range update [l, r] += v dilakukan dengan dua operasi O(1): d[l] += v dan d[r+1] -= v.
Materialisasi array hasil: prefix sum atas d, kompleksitas O(n).
Variasi 2D: empat operasi per submatriks update, materialisasi via prefix sum 2D.
Ideal untuk skenario banyak update + sedikit materialisasi. Untuk pola campuran, gunakan Fenwick tree atau segment tree.