Struktur data biasa bersifat ephemeral: setiap operasi update menimpa state lama. Bila kita ingin akses ke versi historis array — misal “berapa sum [l,r] setelah 1000 update yang lalu?” — struktur data biasa tidak bisa menjawab. Persistent data structure menyimpan semua versi setelah setiap operasi, tanpa mengorbankan kompleksitas update — kita hanya membayar O(log n) ekstra memori per update (path baru dari root ke leaf yang diubah). Aplikasi: undo/redo pada editor, query pada timeline, k-th element pada subarray (persistent segment tree + binary search). Pada Chapter ini kita membangun persistent segment tree lengkap dengan pool node manual, dan menyentuh sketsa persistent DSU.

Aturan: Versi dan Immutability #

Persistent data structure memenuhi: setelah update menghasilkan versi baru v_new, versi lama v_old tetap valid dan dapat diakses kapan saja. Update tidak boleh menimpa node yang dipakai versi lama — harus membuat node baru untuk setiap node yang berubah.

Untuk segment tree point update: hanya node-node di path dari root ke leaf yang di-update yang berubah. Banyaknya = O(log n). Node lain di-share antara versi lama dan versi baru (pointer ke child yang tidak berubah tetap sama).

Mekanisme: Path Copying #

Saat update leaf:

  1. Buat node baru untuk leaf tersebut (jangan ubah leaf lama).
  2. Naik ke parent: buat node parent baru yang left/right child-nya:
    • Child yang berubah: pointer ke node baru hasil rekursi.
    • Child yang tidak berubah: pointer ke child versi lama (di-share, bukan di-copy).
  3. Lanjut rekursi ke root. Total node baru = tinggi tree = O(log n).

Persistent DSU lebih sulit karena path compression memodifikasi banyak node dalam satu find. Solusi: persistent DSU memakai union by rank saja tanpa path compression, dan merekam versi parent array sebagai persistent array (segment tree dengan pointer).

Implementasi Persistent Segment Tree #

cpp 
#include <iostream>
#include <vector>
#include <memory>

struct Node {
    int sum;
    int left, right;  // index anak di pool
    Node() : sum(0), left(0), right(0) {}
};

std::vector<Node> pool;
int new_node() { pool.push_back(Node()); return (int)pool.size() - 1; }

int build(const std::vector<int>& arr, int lo, int hi) {
    int idx = new_node();
    if (lo == hi) {
        pool[idx].sum = arr[lo];
        return idx;
    }
    int mid = (lo + hi) / 2;
    pool[idx].left = build(arr, lo, mid);
    pool[idx].right = build(arr, mid + 1, hi);
    pool[idx].sum = pool[pool[idx].left].sum + pool[pool[idx].right].sum;
    return idx;
}

int update(int prev, int lo, int hi, int pos, int val) {
    int idx = new_node();
    if (lo == hi) {
        pool[idx].sum = val;
        return idx;
    }
    int mid = (lo + hi) / 2;
    if (pos <= mid) {
        pool[idx].left = update(pool[prev].left, lo, mid, pos, val);
        pool[idx].right = pool[prev].right;
    } else {
        pool[idx].left = pool[prev].left;
        pool[idx].right = update(pool[prev].right, mid + 1, hi, pos, val);
    }
    pool[idx].sum = pool[pool[idx].left].sum + pool[pool[idx].right].sum;
    return idx;
}

int query(int root, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;
    if (ql <= lo && hi <= qr) return pool[root].sum;
    int mid = (lo + hi) / 2;
    return query(pool[root].left, lo, mid, ql, qr)
         + query(pool[root].right, mid + 1, hi, ql, qr);
}

int main() {
    pool.reserve(10'000'000);
    pool.push_back(Node());  // dummy di index 0

    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = arr.size();
    std::vector<int> versions;
    versions.push_back(build(arr, 0, n - 1));

    std::cout << "Versi 0 (asli):\n";
    std::cout << "  sum[0,7] = " << query(versions[0], 0, n-1, 0, 7) << '\n';
    std::cout << "  sum[2,5] = " << query(versions[0], 0, n-1, 2, 5) << '\n';

    // Versi 1: update arr[3] = 100
    versions.push_back(update(versions[0], 0, n-1, 3, 100));
    std::cout << "\nVersi 1 (arr[3]=100):\n";
    std::cout << "  sum[0,7] = " << query(versions[1], 0, n-1, 0, 7) << '\n';
    std::cout << "  sum[2,5] = " << query(versions[1], 0, n-1, 2, 5) << '\n';

    // Versi 0 masih utuh!
    std::cout << "\nVersi 0 masih utuh:\n";
    std::cout << "  sum[0,7] = " << query(versions[0], 0, n-1, 0, 7) << '\n';

    // Versi 2: update arr[5] = 50 dari versi 1
    versions.push_back(update(versions[1], 0, n-1, 5, 50));
    std::cout << "\nVersi 2 (dari versi 1, arr[5]=50):\n";
    std::cout << "  sum[0,7] = " << query(versions[2], 0, n-1, 0, 7) << '\n';
    std::cout << "  sum[4,7] = " << query(versions[2], 0, n-1, 4, 7) << '\n';

    std::cout << "\nJumlah node di pool: " << pool.size() << '\n';
    std::cout << "Setiap update hanya menambah sekitar log n (4) node baru\n";
    return 0;
}

Output yang Dihasilkan:

text 
Versi 0 (asli):
  sum[0,7] = 36
  sum[2,5] = 18

Versi 1 (arr[3]=100):
  sum[0,7] = 132
  sum[2,5] = 114

Versi 0 masih utuh:
  sum[0,7] = 36

Versi 2 (dari versi 1, arr[5]=50):
  sum[0,7] = 176
  sum[4,7] = 70

Jumlah node di pool: 24
Setiap update hanya menambah sekitar log n (4) node baru

Bedah Kode Baris-per-Baris #

  1. std::vector<Node> pool: global pool node. Semua node persistent tree disimpan di sini. Indeks integer dipakai sebagai pengganti pointer — lebih hemat memori dan cache-friendly. pool.reserve(10M) pre-alokasi untuk menghindari reallocation (yang akan invalidasi indeks jika address berubah — indeks integer tetap valid, tetapi tetap lebih efisien tanpa realokasi).
  2. new_node(): tambah satu node ke pool, return indeks-nya. Inilah “alokasi” node baru pada persistent tree.
  3. build: post-order rekursif. Setiap internal node menyimpan indeks anak kiri dan kanan di pool. Leaf: sum = arr[lo].
  4. update(prev, lo, hi, pos, val): inti persistent. Buat node baru idx. Bila leaf, set sum = val. Bila bukan, rekursi hanya ke anak yang berubah (sesuai pos), dan share anak yang tidak berubah (pool[idx].right = pool[prev].right artinya versi baru memakai child yang sama dengan versi lama — tidak di-copy). Lalu compute sum baru.
  5. pool[idx].left = update(...): anak kiri adalah node hasil update baru. Anak kanan adalah shared (pointer dari versi lama).
  6. query: identik dengan segment tree biasa — turuni child sesuai query range. Tidak peduli persistent atau tidak; query hanya membaca, jadi aman untuk semua versi.
  7. versions.push_back(...): tiap versi disimpan sebagai indeks root. Akses versi = akses indeks root-nya.
  8. Verifikasi:
    • Versi 0: arr = [1,2,3,4,5,6,7,8], sum[0,7] = 36, sum[2,5] = 3+4+5+6 = 18. ✓
    • Versi 1: arr[3] = 100 → arr = [1,2,3,100,5,6,7,8]. sum[0,7] = 132, sum[2,5] = 3+100+5+6 = 114. ✓
    • Versi 0 masih utuh — sum[0,7] = 36 setelah versi 1 dibuat. Inilah inti persistent.
    • Versi 2: dari versi 1, arr[5] = 50 → arr = [1,2,3,100,5,50,7,8]. sum[0,7] = 176, sum[4,7] = 5+50+7+8 = 70. ✓
  9. Pool 24 node: 1 dummy + 15 (build awal ~2n-1) + 4 (update versi 1) + 4 (update versi 2) = 24. Update hanya menambah O(log n) = 4 node (untuk n=8, log2(8)=3, tapi root baru juga dihitung → 4).

Sketsa Persistent DSU #

Persistent DSU lebih sulit karena find dengan path compression memodifikasi banyak node. Pendekatan standar: gunakan persistent array untuk parent[], dengan union by rank saja (tanpa path compression). Kompleksitas find menjadi O(log² n) (log n untuk traversal find + log n per persistent array access).

cpp 
// Sketsa (pseudo-code):
// PersistentArray menyimpan parent[]. Update indeks i = O(log n) memori baru.
// find(version, x):
//   if PersistentArray[version][x] == x return x;
//   else return find(version, PersistentArray[version][x]);
// unite(v, a, b):
//   ra = find(v, a); rb = find(v, b);
//   if ra == rb return v;
//   if rank[ra] < rank[rb] swap(ra, rb);
//   v_new = PersistentArray.update(v, parent, rb, ra);
//   return v_new;

Persistent DSU dipakai pada offline dynamic connectivity dengan divide-and-conquer on time. Kompleksitas O((n + q) log² n).

Aplikasi Persistent Segment Tree #

  1. K-th smallest in subarray [l, r]: konstruksi persistent segment tree dari awal hingga setiap prefix. Query k-th smallest di [l, r] dengan binary search pada persistent tree: bandingkan count dari tree[r] dan tree[l-1] untuk setiap separuh. O(log n) per query.
  2. Historical range query: jawab range query untuk setiap momen waktu t. O(log n) per query.
  3. Undo/redo editor: simpan persistent rope (string) untuk setiap aksi. Undo = kembali ke versi lama (gratis, O(1)).
  4. 2D range counting: persistent segment tree pada sumbu x, dengan setiap versi merepresentasikan suffix y.

Kompleksitas #

OperasiPersistent segment treeSegment tree biasa
BuildO(n)O(n)
UpdateO(log n) waktu + O(log n) memoriO(log n) waktu
QueryO(log n)O(log n)
Memori totalO(n + m log n)O(n)

Ringkasan #

  • Persistent data structure menjaga semua versi historis tanpa menimpa state lama.
  • Path copying: hanya node di path root-to-leaf yang berubah yang di-copy. Node lain di-share.
  • Persistent segment tree: update O(log n) waktu + O(log n) memori, query O(log n).
  • Pool node global dengan indeks integer lebih efisien dibanding pointer/shared_ptr.
  • Aplikasi: k-th smallest in subarray (classical), historical query, undo/redo editor, offline dynamic connectivity.
  • Persistent DSU memakai persistent array + union by rank tanpa path compression. Kompleksitas O(log² n) per operasi.