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 segment tree, kita dapat melakukannya dengan lebih baik.
Ide Dasar
Ide dasarnya adalah:- Pembagian pertanggungjawaban.
- Cara mendapatkan informasi untuk segmen yang besar dari dua segmen yang lebih kecil.
Barisan kotak-kotak berwarna biru menyatakan array ar, sementara batangan berwarna merah menunjukkan segment tree dengan cakupan yang dilingkupi. Setiap batang akan menyimpan nilai minimal dari nilai-nilai yang dilingkupinya. Misalnya batangan 0 menyimpan nilai minimal dari indeks 0 sampai 7, atau batangan 4 yang menyimpan nilai minimal dari indeks 2 sampai indeks 3. Istilah batang/batangan dapat juga disebut "segmen".
Dengan begitu, ketika ditanya berapa nilai minimal dari indeks 2 sampai 7, cukup cari
nilai terkecil antara batangan 4 dan batangan 2. Perhatikan bahwa keseluruhan elemen dari indeks 2 sampai 7 tercakupi oleh batangan 4 dan 2.
Demikian pula bila ditanya berapa nilai minimal dari indeks 1 sampai 4, cukup cari nilai terkecil antara batangan 8, 4, dan 11.
Sistem ini menjamin bahwa setiap interval yang ditanyakan dapat dicakupi oleh maksimal O(log N) batangan (dengan N adalah besarnya array). Oleh karena itu, setiap query dapat dijawab dalam O(log N).
Lebih jauh lagi, setiap operasi update juga dapat dilakukan dalam O(log N). Maksimal hanya log N batangan yang perlu diperbaharui nilainya.
Misalkan kita mengubah nilai ar[5]. Batangan nomor 12 jelas nilainya berubah menjadi nilai ar[5]. Kita juga perlu memperbaharui nilai batangan 5, batangan 2, dan batangan 0. Caranya:
- Nilai batangan 5: nilai terkecil antara batangan 11 dan batangan 12
- Nilai batangan 2: nilai terkecil antara batangan 5 dan batangan 6
- Nilai batangan 0: nilai terkecil antara batangan 1 dan batangan 2
Implementasi
Segment tree dapat diimplementasikan menjadi sebuah binary tree, yang mana setiap batangan akan kita sebut sebagai node. Anak dari suatu node selalu dua. Node paling atas disebut dengan root, dan node yang tidak memiliki anak lagi disebut leaf. Perhatikan ilustrasi berikut.
Dengan struktur ini, dijamin bahwa setiap node bernomor i memiliki anak bernomor 2i+1 dan 2i+2. Hal ini mempermudah kita dalam penyimpanan data karena kita tidak perlu mengimplementasikan tree dengan representasi graf (misal: adjacency list). Untuk contoh di atas, kita cukup gunakan array dengan ukuran 15 elemen. Akses anak dari suatu node i dilakukan dengan mengambil indeks 2i+1 dan 2i+2.
Catatan: apabila array dimulai dari angka 1, berarti anak node i adalah 2i dan 2i+1.
Lalu berapa banyak node yang dibutuhkan segment tree untuk N elemen?
Bila ditelusuri dari root ke leaf, yang dibutuhkan adalah 1+2+4+8+...+2D sehingga 2D lebih dari atau sama dengan N. Jumlahan deret itu sama dengan 2D+1-1.
Jadi cukup cari bilangan 2 pangkat yang lebih atau sama dengan N, lalu dikali 2 saja. Nilai ini paling besar mendekati 4N, sehingga memori yang diperlukan adalah O(N).
Kalau Anda sering ikut kontes programming dan butuh cepat-cepat, angka perlu dihafal adalah:
- 131.072 (217), untuk N=100.000. Saya biasa ingatnya 132.000 saja.
- 1.048.576 (220), untuk N=1.000.000. Saya biasa ingatnya 1.050.000 saja.
Kembali ke implementasi segment tree, pertama buat dulu array global untuk menampung nilai setiap batangan. Anggap saja kali ini N=100.000.
Selanjutnya, kita bisa menulis prosedur untuk membangun segment tree untuk pertama kalinya.
Variabel id menyatakan indeks batangan yang akan dibuat, sementara l dan r menyatakan cakupan batangan. Prosedur perlu dipanggil dengan "build(0, 0, N-1)", sebab batangan pertama memiliki indeks 0, dan mencakup indeks 0 sampai N-1.
Untuk implementasi query, kita dapat melakukannya secara rekursif dari node 0. Apabila node saat ini dikandung oleh rentang diinginkan, cukup kembalikan nilai yang disimpan pada node tersebut. Selain daripada itu, pecah menjadi 2 dan kumpulkan jawaban dari anak-anaknya yang menyentuh rentang yang diinginkan. Pemanggilan pertama dapat dilakukan dengan "query(0, 0, N-1, x, y)".
Terakhir, untuk update lakukan juga secara rekursif dari node 0 sampai leaf tercapai. Jangan lupa untuk memperbaharui nilai batangannya setelah anaknya di-update.
Dan selesailah implementasinya. Berikut implementasi lengkapnya.
Latihan
Untuk latihan segment tree klasik, coba kerjakan SPOJ THRBL.Ada sedikit jebakan-jebakan pada cara menerjemahkan inputnya ke query, tetapi konsep segment tree-nya klasik.
Abstraksi Segment Tree
Setelah Anda menguasai konsep segment tree, akan tiba saatnya Anda perlu segment tree yang aneh-aneh. Misalnya perlu menyimpan lebih dari 1 nilai.Secara umum, template abstrak berikut dapat digunakan:
Selama Anda bisa mendefinisikan fungsi:
- CREATE(v): menciptakan sebuah node segment tree dari nilai sebuah elemen array berupa v
- MERGE(vl, vr): menggabungkan dua node segment tree yang bersebelahan menjadi sebuah node yang lebih besar
maka Anda dapat membuat segment tree untuk kasus yang lebih kompleks. Pada contoh yang kali ini kita bahas, definisinya adalah:
- CREATE(v): cukup kembalikan nilai v. Sebab nilai terkecil untuk sebuah elemen array berupa v adalah v itu sendiri.
- MERGE(vl, vr): kembalikan nilai terkecil antara vl dan vr. Sebab nilai terkecil dari array dengan indeks yang dicakup node berisi vl dan vr jelas adalah nilai terkecil dari keduanya.
Pada kasus segment tree yang menyimpan lebih dari 1 nilai, CREATE dan MERGE menjadi tidak sesederhana yang kita bahas di sini. Coba baca tulisan saya sebelumnya tentang variasi nilai agregat.
Konsep CREATE dan MERGE ini sangat erat dengan konsep divide and conquer.
Bagian yang rawan bug adalah bagian pemeriksaan rentangnya, yang digunakan pada kondisi if. Salah mengetikkan batasannya dapat menghasilkan bug yang susah dideteksi. Jadi pahami betul-betul bagian sana.
Ada 1 bagian yang belum saya bahas di sini, yaitu range update. Implementasi range update perlu dibuat dengan "lazy propagation". Kita akan membahasnya dan abstraksinya pada kesempatan yang akan datang.
Penutup
Perkenalan ini lebih dititikberatkan pada cara menulis kodenya yang berlaku secara umum, sehingga kerangka kodenya dapat dipakai untuk kasus segment tree lainnya.Saat saya pertama kali coding segment tree, saya bingung karena penulisan kode di buku CP, dari asisten TOKI, atau sumber internet berbeda-beda. Diperlukan ekstra usaha untuk mendekomposisi apa saja yang perlu dilakukan saat build, query, dan update.
Dengan tulisan ini saya harap pembaca jadi tahu komponen abstrak dari segment tree itu apa saja dan menerapkannya pada macam-macam masalah yang dihadapi.
Tidak ada komentar :
Posting Komentar