Saturday, 6 December 2014

Persistent Data Structure

Kali ini saya akan memperkenalkan suatu struktur data yang sangat menarik, yaitu persistent data structure. Struktur data ini sebenarnya adalah modifikasi dari struktur data yang sudah ada, seperti segment tree atau BST. Saya akan menerangkannya mulai dari permasalahan.

Permasalahan Motivasi

Diberikan sebuah array A berisi N bilangan. Indeks dari A dinomori dari 0 sampai N-1. Diberikan pula Q operasi yang bisa berupa:
  • Update x y, yang artinya laksanakan A[x] = y
  • Query x y z, yang artinya cari min(A[x], A[x+1], A[x+2], ..., A[y]) pada array A sebelum operasi update ke-z dilaksanakan

Nah lho, bagaimana jika N dan Q bisa sampai 100.000? Tidak mungkin kita menyimpan setiap versi dari array A kan?

Persistent Segment Tree

Seandainya setiap query dilaksanakan pada array A versi terakhir, maka kita bisa menerapkan struktur data segment tree seperti biasa.

Coba perhatikan versi pertama dari array A. Saya sebut versi ini sebagai "versi 0".

Jika dilakukan update pada A[5], didapatkan versi 1 dari array A. Perhatikan segmen-segmen yang di-update:

Tentu saja, kita kehilangan informasi dari versi 0 array A. Namun, perhatikan lebih lanjut bahwa hanya O(log N) segmen saja yang berubah, sementara sisanya tetap sama.

Jadi, bagaimana kalau dibuat saja "cascading segment tree"? Kita buat segment tree baru, tetapi menggunakan sebagian besar data yang ada pada segment tree versi sebelumnya.


Kita akan menambahkan sebanyak O(log N) node baru pada segment tree yang baru ini. Anak kiri dan anak kanan dari setiap node yang baru ditentukan dari elemen mana yang diubah. Dengan mengingat setiap root node dari setiap versi, kita bisa mendapatkan informasi segment tree untuk setiap versi! Coba saja pandang segment tree yang memiliki root di versi 1!

Kini, setiap update dapat dilaksanakan dalam O(log N) dan menambah kompleksitas memori sebesar O(log N) juga, dan setiap query bisa dilakukan dalam O(log N). Cukup untuk N dan Q hingga ratusan ribu.

Implementasi

Tentu saja ada macam-macam implementasi yang bisa Anda gunakan. Saya menyarankan untuk menghindari penggunaan pointer, karena menambah konstanta yang besar dan mungkin saja algoritma O(N log N) Anda TLE untuk N = 100.000 (saya pernah mengalaminya).

Cara yang saya sarankan adalah membuat semua struct-nya dalam array 1 dimensi, lalu indeksnya menjadi id bagi setiap node. Detilnya bisa dilihat pada implementasi berikut:

Generalisasi

Tidak hanya segment tree yang bisa dibuat versi persistent-nya. Struktur data seperti BBST (misalnya AVL atau treap) juga bisa. Silakan perkuat kemampuan implementasi Anda, karena sepengalaman saya tidak mudah untuk mengimplementasikan persistent BBST.

Latihan


syntax highlighting tutorial

2 comments :

  1. Penjelasan yang sangat detail! Saya langsung mengerti. Terima kasih banyak m(-_-)m.

    Buat tutorial suffix array dong kak. Atau Max Flow.

    ReplyDelete
    Replies
    1. Halo, syukurlah kalau tulisannya membantu :)

      Untuk suffix array dan max flow, mungkin saya tidak menjelaskan algoritmanya. Di buku competitive programming udah cukup jelas soalnya. Kalau untuk variasi dan penyelesaian soal mungkin akan saya bahas

      Delete