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.
Nah lho, bagaimana jika N dan Q bisa sampai 100.000? Tidak mungkin kita menyimpan setiap versi dari array A kan?
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.
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:
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.
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:
Penjelasan yang sangat detail! Saya langsung mengerti. Terima kasih banyak m(-_-)m.
BalasHapusBuat tutorial suffix array dong kak. Atau Max Flow.
Halo, syukurlah kalau tulisannya membantu :)
HapusUntuk 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