Thursday, 11 July 2013

Tentang Segment Tree: Variasi Nilai Agregat

Bagian yang sebelumnya menunjukkan bahwa setiap node dalam segment tree bisa saja menyimpan lebih dari satu nilai. Nilai-nilai yang disimpan dalam suatu node seperti sum dan prop pada contoh di atas disebut dengan nilai agregat.

Hal yang membuat segment tree menjadi struktur data yang serba bisa sebenarnya adalah nilai agregat ini, digabungkan dengan prinsip pembagian pertanggungjawaban. Nilai agregat ini bisa berupa apa saja, nilai maksimum, jumlahan elemennya, hasil perkalian, banyaknya pola tertentu yang muncul, subsekuens konsekutif dengan jumlahan maksimal, sebuah himpunan, dan sebagainya. Bandingkan dengan struktur data untuk menjawab dynamic range query lainnya seperti BIT, yang nilai agregatnya cukup terbatas.

Contoh berikut akan menunjukkan bagaimana nilai agregat pada node menjadikan segment tree sangat berguna. Diberikan sebuah array A. Terdapat dua macam operasi:
  1. update(a, b), artinya mengubah elemen di indeks ke-a menjadi b.
  2. query(a, b), artinya mencari jumlahan maksimum sekuens konsekutif yang ada di antara indeks a sampai indeks b (inklusif). Misalnya untuk [1, 4, -9, 3, 2, -1, 3, -7], jumlahan maksimum sekuens konsekutifnya ada pada [3, 2, -1, 3], yaitu 7. Kita akan menyebut subsekuens konsekutif ini subsekuens konsekutif maksimum.
Untuk persoalan ini, diharapkan kedua operasi dapat dilaksanakan lebih cepat dari O(N). Bagaimana implementasi segment tree-nya? Sekilas soal ini bahkan tidak dapat diselesaikan dengan segment tree!

Perhatikan bahwa prinsip dari segment tree adalah pembagian pertanggungjawaban. Oleh karena itu, setiap node perlu menyimpan nilai jumlahan subsekuens konsekutif maksimum yang ada pada interval yang dilingkupinya. Lalu bagaimana dengan peristiwa update? Kita perlu suatu mekanisme yang memungkinkan parent node bisa memperbaharui nilainya dengan informasi dari left child dan right child-nya. Oleh karena itu, suatu node x yang melingkupi indeks a sampai b perlu menyimpan nilai agregat-agregat berikut:
  1. Nilai subsekuens konsekutif maksimal di antara A[a], A[a+1], A[a+2], ..., A[b], kita sebut dengan mmax.
  2. Nilai subsekuens konsekutif maksimum yang bermula di A[a] dan berakhir di A[i] dengan a ≤ i ≤ b, kita sebut dengan lmax.
  3. Nilai subsekuens konsekutif maksimum yang bermula di A[i] dan berakhir di A[r] dengan a ≤ i ≤ b, kita sebut dengan rmax.
  4. Jumlah dari A[a] + A[a+1] + A[a+2] + ... + A[b], kita sebut dengan sum

Perhatikan gambar berikut untuk lebih jelasnya.

Dengan begitu, parent node bisa memperbaharui nilainya cukup dengan informasi dari child node dengan:
  1. parent.mmax = max(leftChild.mmax, rightChild.mmax, leftChild.rmax + rightChild.lmax)
  2. parent.lmax = max(leftChild.lmax, leftchild.sum + rightChild.lmax)
  3. parent.rmax = max(rightChild.rimax, rightChild.sum + leftChild.rmax)
  4. parent.sum = leftChild.sum + rightChild.sum
Perhatikan gambar berikut untuk memperjelas proses penggabungan nilai parent dari anak-anaknya.

Dengan pengetahuan itu, melakukan update terhadap struktur segment tree tidak menjadi masalah, karena kita selalu bisa memperbaharui nilai node dengan benar dan efisien (O(log N)). Sebagai latihan, Anda dapat mencoba mengerjakan soal di SPOJ (Sphere Online Judge) dengan kode persoalan GSS1.

Persoalan segment tree yang keluar dalam kontes seperti codeforce, ICPC, atau Pelatnas biasanya menantang Anda untuk mencari nilai agregat apa yang perlu disimpan. Sebagai latihan, Anda dapat mencoba mengerjakan juga:

Codeforces 52C - Circular RMQ


SPOJ - MULTQ3


SPOJ - RPAR


UVa 11402 - Ahoy Pirates


Codeforces 85D - Sum of Medians


SPOJ - MKTHNUM


Curhat colongan: ketika baru belajar segment tree, saya kira gunanya hanya untuk RMQ (mencari maks/min dari interval). Begitu di Pelatnas 2 TOKI 2011 saya langsung kaget dan tidak berdaya dengan soal segment tree. Bahkan hingga akhir IOI 2011, saya belum menguasai betul materi ini. Baru setelah Pelatnas 3 TOKI 2012 dimana saya menjadi asisten, bisa mengerti lebih jauh tentang struktur data ini. Semoga tulisan ini dapat membuka wawasan Anda tentang segment tree dan mengaplikasikannya dalam menyelesaikan persoalan yang (biasanya) sulit.

No comments :

Post a Comment