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

Bagian sirkulernya tidak terlalu menjadi masalah, yang penting adalah anda tahu bagaimana menjalankan operasi tersebut pada array yang tidak sirkuler. Perhatikan bahwa jika nilai minimum di suatu interval adalah x, lalu interval itu ditambah dengan d, maka nilai minimumnya adalah x+d.

SPOJ - MULTQ3

Simpan 3 nilai agregat: banyaknya elemen yang bila dibagi 3 hasilnya 0, banyaknya elemen yang bila dibagi 3 hasilnya 1, dan banyaknya elemen yang bila dibagi 3 hasilnya 2.
Anda dapat menggunakan prinsip lazy propagation untuk melayani update dan manipulasi nilai agregat itu.
Hati-hati dengan time limit yang sangat ketat, solusi O(N log N) saya mendapat TLE hanya karena sering menggunakan operasi mod (%).

SPOJ - RPAR

Simpan 4 nilai agregat: nilai a, b, c, dan ada atau tidaknya nilai yang perlu dipropagasi.
Anda dapat juga menggunakan prinsip lazy propagation untuk melayani update dan manipulasi nilai agregat itu.

UVa 11402 - Ahoy Pirates

Agak rumit, tetapi yang perlu anda simpan adalah: banyaknya Buccaneer di interval itu, dan keadaan interval ini apakah sedang dalam pengaruh sihir F, E, atau I. Lagi-lagi, gunakan lazy propagation.

Codeforces 85D - Sum of Medians

Akhirnya saya selesaikan berkat petunjuk dari Pak Suhendry. Baca dulu semua masukan dan lakukan grid compression. Buat segment tree yang isinya 0 semua. Berikutnya untuk suatu interval, simpan berapa jumlahan elemen yang indeksnya bila dibagi 5 hasilnya 0, hasilnya 1, 2, ..., sampai yang hasilnya 4. Dengan cara ini mencari "jumlahan median" dan update dapat dilaksanakan dalam O(log N).

SPOJ - MKTHNUM

Berpikirlah dengan cara yang lain, tanpa hanya mengandalkan nilai agregat. Misalkan kita anggap x sebagai jawabannya, apa ciri bahwa x adalah bilangan ke-k terkecil dalam rentang tersebut?

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.