Tentang Segment Tree: Lazy Propagation

Dari beberapa postingan yang saya buat, terdapat istilah lazy propagation pada segment tree. Mungkin di antara kalian ada yang belum tahu apa itu segment tree, apalagi lazy propagation. Nah untuk kalian yang belum tahu tentang segment tree, disarankan untuk membaca ulasannya di tutorial FPC Ristek Fasilkom UI.

UPDATE 1: sekarang webnya sudah musnah, termasuk tulisan-tulisan saya.
UPDATE 2: back up tulisan saya sudah dituangkan ke petunjuk coding segment tree.

Tulisan ini akan difokuskan dalam lazy propagation.

Salah satu keunggulan dari segment tree adalah kemudahannya dalam melakukan lazy propagation. Teknik ini biasanya digunakan ketika diperlukan update pada suatu interval (bukan suatu elemen). Sebagai contoh, misalkan diberikan array ar yang seluruh elemennya bernilai 0 dan sejumlah operasi:

1. update(a, b, c), yang artinya menambah isi dari ar[a], ar[a+1], ..., ar[b] dengan c.
   
2. query(a, b), yang artinya mencari jumlahan dari ar[a], ar[a+1], ..., dan ar[b].

Bila operasi update hanya dilakukan pada suatu elemen, tentunya permasalahan ini dapat dengan mudah dengan segment tree. Sayangnya, dengan update suatu interval kita tidak mungkin menginterasi setiap elemen dan melakukan update pada elemen tersebut karena kompleksitasnya akan menjadi O(N).

Solusi yang lebih baik adalah dengan melakukan update secara lazy.
Prinsipnya adalah selama setiap operasi di suatu interval bisa ditunda, maka tunda hingga tidak bisa lagi ditunda (terdengar agak aneh). Artinya, di setiap node segment tree kita akan menyimpan operasi-operasi yang tertunda. Berhubung operasinya hanya berupa penjumlahan, maka setiap node cukup menyimpan banyaknya jumlahan yang seharusnya sudah ditambahkan hingga ke leaf node yang ada di bawah node tersebut tetapi masih tertunda. Oleh karena itu, setiap node perlu menyimpan dua nilai: jumlahan yang dia cakupi (tidak termasuk yang seharusnya dilaksankan) dan jumlahan yang seharusnya dia laksanakan. Kedua nilai ini akan dinyatakan dengan nama "sum" dan "prop".

Sebagai contoh, N = 8 dan kita perlu melakukan update di indeks ke-2 sampai 7, ditambah dengan 5. Normalnya, operasi tersebut harus dilaksanakan sampai leaf node, yaitu node 9, 10, 11, ..., 14. Namun dengan prinsip lazy, kita tunda operasi tersebut di node yang mewakili indeks-indeks tersebut. Dengan kata lain, prop untuk node 4 dan 2 bertambah sebanyak 5 (sementara nilai sum mereka tetap 0). Node di gambar berikut ini yang berwarna jingga menyatakan ada operasi yang tertunda di sana:

Pada segment tree biasanya, jika diperlukan query dari indeks 1 sampai 7, tinggal ambil nilai-nilai dari node 8, 4, dan 2. Untuk kasus ini,

node 4 dan 2 perlu mengembalikan sum + (r - l + 1)*prop dengan [l, r] adalah batas indeks-indeks yang dicakupi node tersebut. Sebagai contoh, node 2 perlu mengembalikan sum + (7-4+1)*prop. Mengapa? Karena masing-masing dari 4 elemennya seharusnya ditambahkan dengan prop (tetapi ditunda).

Demikian pula ketika kita mau melakukan update dari indeks 2 sampai dengan 5, misalnya ditambahkan dengan 11. Cukup node-node yang mewakili indeks tersebut yang perlu di-update. Bedanya, kali ini kita tidak bisa semata-mata menambahkan nilai prop node 2 dengan 11 atau 22. Kita harus melaksanakan operasi yang tertunda di node 2 tadi, tetapi tetap dengan prinsip lazy. Artinya, node 5 dan 6 akan menerima tambahan untuk nilai prop mereka sebesar 5 (dari operasi yang pertama). Setelah itu, baru dilanjutkan update yang tadi, dimana pada akhirnya node 5 akan menerima tambahan nilai prop sebesar 11. Perhatikan bahwa node 2 saat itu akan memiliki nilai prop = 0, dan nilai sum-nya diperbaharui dari nilai-nilai node 5 dan 6. Untuk klarifikasi, (sum, prop) dari node 2 adalah (42, 0) (42 dari 32 + 10), node 5 adalah (0, 16), dan node 6 adalah (0, 5).

Sebelumnya, kita sudah membahas bagaimana jika saat operasi query, informasi yang diperlukan berada tepat pada suatu interval yang dicakupi sebuah node yang menyimpan penundaan operasi (misalnya [4, 7] di node 2). Namun bagaimana ketika yang diperlukan adalah query dari indeks 1 sampai 4? Yang kita perlukan adalah jumlahan dari nilai node 8, 4, dan 11. Nilai node 11 tidak bisa didapatkan langsung karena di atasnya terdapat operasi yang tertunda (di node 5). Untuk itu, ketika fungsi rekursif untuk query mencapai node 5 dan hendak ke node 11, kita laksanakan operasi yang tertunda itu. Sehingga node 11 dan 12 akan menerima tambahan prop sebesar 16. Setelah ini, nilai setiap node 8, 4, dan 11 bisa diketahui.

Bila diperhatikan, setiap kali suatu operasi tertunda di node x hendak dilaksanakan, kita cukup menambahkan anak kiri dan kanan node x dengan prop yang dimiliki x. Operasi ini biasa disebut sebagai propagate, dimana kita "menyalurkan" informasi dari orang tua node ke anak kiri dan kanannya.

Dari contoh tersebut, bisa ditarik kesimpulan:

1. Saat operasi update, bila interval yang perlu di-update sepenuhnya dicakupi node tersebut, tunda operasinya. Bila tidak, propagate node tersebut, baru laksanakan update ke anak kiri dan/atau kanannya.
2. Saat operasi query, bila interval yang perlu diperlukan informasinya sepenuhnya dicakupi node tersebut, kembalikan sum + (r - l +1)*prop dari node tersebut. Bila tidak, propagate node tersebut, baru cari informasinya dengan query ke anak kiri dan/atau kanannya. Setelah itu, perbaharui nilai sum dan prop pada node itu.
   

Dengan cara ini, dicapai kompleksitas O(log N) untuk setiap operasi baik update maupun query. Sebagai latihan, anda dapat mencoba mengerjakan soal di SPOJ (Sphere Online Judge) dengan kode persoalan HORRIBLE (di sini).

Untuk lebih memahami bagaimana mengimplementasikannya, baca tulisan saya tentang petunjuk coding: segment tree lazy propagation.