Senin, 07 Januari 2019

Petunjuk Coding: Segment Tree Lazy Propagation

Setelah menguasai penulisan kode segment tree yang melayani update sebuah elemen dan range query, kini waktunya beranjak ke operasi yang lebih sulit: range update.

Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.


Konsep

Lazy propagation dapat diimplementasikan ketika:
  1. Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
  2. Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.
Apabila kedua syarat itu dipenuhi, maka lazy propagation dapat diterapkan. Setiap range update atau query dapat dilaksanakan dalam O(log N).

Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".

Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.

Rabu, 02 Januari 2019

Petunjuk Coding: Segment Tree

Sebenarnya tulisan ini mau difokuskan ke implementasi segment tree. Tapi karena tulisan saya sebelumnya di ristekfasilkom.com sudah musnah (hosting-annya habis), jadinya saya kembalikan back-up tulisannya ke sini.

Segment tree merupakan struktur data yang biasa dipakai untuk menjawab dynamic range
query, yaitu sejumlah operasi yang dilakukan dengan rentang yang bervariasi. Selama tidak ada penyisipan atau penghapusan elemen, segment tree hampir selalu bisa digunakan. Tulisan ini akan membahas tentang konsep struktur data ini dan cara implementasinya.


Permasalahan Motivasi

Diberikan sebuah array integer dan serangkaian operasi.
Sebut saja array itu adalah ar. Operasi-operasi yang diberikan bisa berupa:
  • update(x, v), yang artinya mengubah isi ar[x] menjadi v.
  • query(x, y), yang artinya mencari nilai minimum dari ar[x], ar[x+1], ..., ar[y].
Dengan cara naif, update dapat dilaksanakan dalam O(1). Sementara query dapat dilaksanakan dalam O(N), dengan N adalah panjang array. Tentunya cara ini kurang efisien, khususnya jika N cukup besar dan operasi yang diberikan cukup banyak.

Dengan segment tree, kita dapat melakukannya dengan lebih baik.