Difference array 1D sudah dibahas di Chapter Difference Array di Section Array . Pada Chapter meta ini kita akan fokus pada aplikasi tingkat lanjut: 2D difference array (range update kotak O(1)), event counting via diff (menghitung overlap interval tanpa struktur berat), dan paint problem (lapisan cat dengan prioritas). Ketiga aplikasi memamerkan kekuatan difference technique: mengubah batch operasi berat menjadi beberapa operasi elementer.

Recap: Difference Array 1D #

Untuk array a, definisikan d[i] = a[i] - a[i-1]. Update “tambah v ke a[l..r]” = d[l] += v; d[r+1] -= v;. Setelah semua update, rekonstruksi a dengan prefix sum. Kompleksitas: O(1) per update, O(n) rekonstruksi. Lihat Chapter sebelumnya untuk kode lengkap.

Aplikasi 1: Difference Array 2D #

Aturan #

Diberikan matriks a berukuran n × m awalnya 0, lalu q operasi: “tambah v ke semua sel di kotak (r1, c1) → (r2, c2)”. Cetak matriks akhir. Solusi naif: O(q · n · m). Dengan 2D difference array: O(q + n·m).

Mekanisme: Empat Titik Sudut #

Perluasan dari 1D: kita tandai empat titik sudut pada matriks d berukuran (n+1) × (m+1):

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 untuk mendapatkan matriks akhir.

Kode: 2D Difference Array #

cpp 
#include <iostream>
#include <vector>

class DiffArray2D {
public:
    DiffArray2D(int n, int m) : n_(n), m_(m), d(n + 2, std::vector<long long>(m + 2, 0)) {}

    void 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;
    }

    std::vector<std::vector<long long>> finalize() const {
        std::vector<std::vector<long long>> a(n_, std::vector<long long>(m_, 0));
        for (int i = 0; i < n_; ++i) {
            for (int j = 0; j < m_; ++j) {
                long long cur = d[i][j];
                if (i > 0) cur += a[i-1][j];
                if (j > 0) cur += a[i][j-1];
                if (i > 0 && j > 0) cur -= a[i-1][j-1];
                a[i][j] = cur;
            }
        }
        return a;
    }

private:
    int n_, m_;
    std::vector<std::vector<long long>> d;
};

int main() {
    DiffArray2D da(5, 5);
    da.add(0, 0, 2, 2, 3);  // kotak kiri-atas 3x3 += 3
    da.add(1, 1, 4, 4, 5);  // kotak 4x4 += 5
    da.add(2, 2, 3, 3, -2); // kotak 2x2 -= 2

    auto m = da.finalize();
    std::cout << "Matriks akhir:\n";
    for (const auto& row : m) {
        for (long long x : row) std::cout << x << '\t';
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Matriks akhir:
3       3       3       0       0       
3       8       8       5       5       
3       8       6       3       5       
0       5       3       3       5       
0       5       5       5       5
  1. Baris d(r1, c1, r2, c2, v) empat baris pertama: tandai empat sudut. Pola: dua += v di sudut “kanan-bawah” dua kali (untuk kompensasi), dua -= di sudut tengah.
  2. Alokasi d(n + 2, ...): ukuran n+2 agar d[r2+1][c2+1] aman saat r2 = n-1, c2 = m-1.
  3. Block finalize: lakukan prefix sum 2D inklusi-eksklusi. cur = d[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]. Hasilnya matriks a akhir.
  4. Hasil a[1][1] = 8: dua update mencakup sel ini — [0,0..2,2]+3 dan [1,1..4,4]+5 → 3 + 5 = 8. Sesuai.
  5. Hasil a[2][2] = 6: tiga update mencakup sel ini — +3, +5, -2 → 3 + 5 - 2 = 6. Sesuai.

Aplikasi 2: Event Counting via Difference #

Aturan #

Diberikan n interval [l_i, r_i] (integer, inclusive). Hitung berapa interval yang mencakup setiap titik di rentang [1, M]. Solusi naif: O(n · M). Dengan difference: O(n + M).

Mekanisme: Interval sebagai Update #

Setiap interval [l, r] adalah “tambah 1 ke cnt[l..r]”. Ini persis range update 1D dengan v = 1. Setelah semua update, prefix sum memberi jumlah interval per titik.

Kode: Interval Coverage Counting #

cpp 
#include <iostream>
#include <vector>

std::vector<long long> coverage(const std::vector<std::pair<int,int>>& intervals, int M) {
    std::vector<long long> d(M + 2, 0);
    for (auto [l, r] : intervals) {
        d[l] += 1;
        d[r + 1] -= 1;
    }
    std::vector<long long> cnt(M + 1, 0);
    long long cur = 0;
    for (int i = 1; i <= M; ++i) {
        cur += d[i];
        cnt[i] = cur;
    }
    return cnt;
}

int main() {
    std::vector<std::pair<int,int>> intervals = {
        {1, 5}, {2, 3}, {4, 8}, {3, 6}, {7, 9}
    };
    int M = 10;
    auto cnt = coverage(intervals, M);
    std::cout << "Titik\tCount\n";
    for (int i = 1; i <= M; ++i) {
        std::cout << i << '\t' << cnt[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Titik   Count
1       1
2       2
3       3
4       3
5       3
6       2
7       2
8       2
9       1
10      0
  1. Baris d[l] += 1; d[r + 1] -= 1;: setiap interval diwakili dua operasi difference. Sepasang +1/-1 menandai rentang cakupan.
  2. Baris cur += d[i]; cnt[i] = cur;: rekonstruksi prefix sum. cnt[i] = jumlah interval yang mencakup titik i.
  3. Hasil Titik 3 = 3: interval [1,5], [2,3], [3,6] mencakup titik 3. Sesuai.
  4. Hasil Titik 6 = 2: interval [1,5] (5 < 6, tidak mencakup), [3,6] (ya), [4,8] (ya), [7,9] (tidak). Total 2. Sesuai.

Aplikasi 3: Paint Problem dengan Prioritas #

Aturan #

Diberikan dinding 1D dengan n sel. Lakukan q operasi cat: paint(l, r, color) — cat sel l..r dengan warna color. Cat terakhir menutup cat sebelumnya. Tentukan warna akhir setiap sel. Solusi naif: O(q · n). Solusi difference + iterasi terbalik: O(q + n).

Mekanisme: Iterasi dari Belakang #

Bila kita iterasi update dari akhir ke awal, sekali sebuah sel dicat, warna final sudah ditentukan — update yang lebih awal tidak relevan untuk sel itu. Kita perlu struktur untuk melacak sel yang sudah dicat. Solusi sederhana: gunakan DSU (Disjoint Set Union) dengan pointer “sel berikutnya yang belum dicat”.

Kode: Paint Problem dengan DSU #

cpp 
#include <iostream>
#include <vector>

struct DSU {
    std::vector<int> parent;
    explicit DSU(int n) : parent(n + 2) {
        for (int i = 0; i <= n + 1; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) parent[px] = py;
    }
};

std::vector<int> paint(int n, const std::vector<std::tuple<int,int,int>>& ops) {
    std::vector<int> color(n + 1, -1);
    DSU dsu(n + 1);
    // Iterasi dari belakang
    for (auto it = ops.rbegin(); it != ops.rend(); ++it) {
        auto [l, r, c] = *it;
        int pos = dsu.find(l);
        while (pos <= r) {
            color[pos] = c;
            dsu.unite(pos, pos + 1);
            pos = dsu.find(pos);
        }
    }
    return color;
}

int main() {
    int n = 10;
    std::vector<std::tuple<int,int,int>> ops = {
        {1, 6, 1},   // warna 1 pada [1,6]
        {3, 8, 2},   // warna 2 pada [3,8] (override 1 di [3,6])
        {2, 4, 3},   // warna 3 pada [2,4] (override 2 di [3,4] dan 1 di [2])
        {7, 9, 4}    // warna 4 pada [7,9]
    };
    auto c = paint(n, ops);
    std::cout << "Sel\tWarna\n";
    for (int i = 1; i <= n; ++i) {
        std::cout << i << '\t' << c[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Sel     Warna
1       1
2       3
3       3
4       3
5       2
6       2
7       4
8       4
9       4
10      -1
  1. Struktur DSU: setiap sel i awalnya punya parent i sendiri. find(i) mengembalikan sel terkecil ≥ i yang belum dicat. unite(i, i+1) menggabungkan, sehingga find(i) berikutnya melompat ke sel berikutnya.
  2. Baris for (auto it = ops.rbegin(); ...): iterasi operasi cat dari yang terakhir (warna paling atas) ke yang pertama.
  3. Baris int pos = dsu.find(l);: temukan sel pertama di [l, r] yang belum dicat.
  4. Baris color[pos] = c;: cat sel tersebut dengan warna operasi saat ini.
  5. Baris dsu.unite(pos, pos + 1);: tandai pos sebagai sudah dicat — find(pos) berikutnya lompat ke pos+1.
  6. Baris pos = dsu.find(pos);: lompat ke sel berikutnya yang belum dicat dalam rentang.
  7. Hasil Sel 3 = 3: operasi terakhir yang mencakup sel 3 adalah {2,4,3} dengan warna 3. Sesuai (operasi {3,8,2} lebih awal).
  8. Hasil Sel 10 = -1: tidak ada operasi yang mencakup sel 10. Tidak tercatat (-1 sentinel).

Ringkasan #

  • 2D difference array: empat titik sudut per kotak update, prefix sum 2D untuk rekonstruksi. O(q + n·m).
  • Event counting via diff: interval = +1/-1 di ujung; prefix sum memberi cakupan per titik. O(n + M).
  • Paint problem dengan DSU: iterasi operasi terbalik, gunakan DSU untuk skip sel yang sudah dicat. Amortized O((n + q) · α(n)).
  • Difference technique adalah invers dari prefix sum. Banyak soal “batch range update” dapat dijawab dengan kombinasi keduanya.