Pohon Segmen

1. Introduction

Sebuah pohon segmen (Segment Tree / ST) adalah pohon biner yang dibuat berdasarkan sebuah array (biasanya bilangan bulat) supaya kita dapat menyelesaikan query Range Min/Max/Sum (biasa disingkat RMinQ/RMaxQ/RSumQ, variasi lainnya juga memungkinkan) serta query Range (termasuk Point) Update pada array tersebut dalam O(log N) dibandingkan dengan cara naif dalam O(N). Dengan sebuah array A dari N element, kita dapat membuat pohon segmen RMinQ/RMaxQ/RSumQ dalam waktu O(N).

2. Mode

Untuk berpindah antara Pohon Segmen RMinQ/RMaxQ/RSumQ, pilihlah header yang sesuai. Catat bahwa mungkin terdapat tipe range query selain tiga contoh klasik dalam visualisasi ini.

3. Visualisasi - Sisi Atas

Lihatlah visualisasi dari Pohon Segmen (pohon di atas larik) di sini!

Pohon di sisi atas merupakan struktur Pohon Segmen. Simpul-simpul diindeks serupa dengan suatu strukture data Binary Heap di mana akarnya berada di indeks 1 dan anak kiri/kanan dari sebuah simpul p adalah 2*p/2*p+1, masing-masing. Nilai dalam tiap simpul menunjukkan nilai MinIndex/MaxIndex/Sum dari segmen [L, R] yang bersangkutan dari larik A. Kami memberi "p:[L,R]" berwarna merah di bawah setiap simpul kecuali jika L=R dan segmen tersebut bersangkutan dengan satu indeks pada larik (hanya indeks tersebut yang ditunjukkan).


Simpul-simpul yang di-update seperlunya (lazy update) akan memiliki highlight cincin ungu. Teknik lazy update ini akan dijelaskan di slide-slide berikutnya.

3-1. Visualisasi - Sisi Bawah

Baris bawah menunjukkan nilai awal array A (berwarna kuning) yang digunakan untuk membuat Pohon Segmen.
Setiap simpul daun pada Pohon Segmen bersangkutan dengan sebuah indeks individu pada larik A. Untuk Pohon Segmen Min dan Max, simpul daun dari Pohon Segmen mempunyai indeks tersebut (elemen minimum/maksimum dari sebuah sub-larik dengan satu elemen adalah elemen tersebut). Untuk Pohon Segmen Sum, simpul daun pada Pohon Segmen mempunyai nilai dari satu elemen tersebut.

4. Operasi

Terdapat tiga operasi dasar yang tersedia pada visualisasi struktur data Pohon Segmen (untuk tiap mode: RMinQ/RMaxQ/RSumQ):
1. Anda dapat membuat pohon segmen RMinQ/RMaxQ/RSumQ dari array integer masukkan anda sendiri (maksimum terdiri dari 16 integer 2 digit), atau membiarkan sistem menyediakan sebuah integer (acak) kecil atau sebuah array (terurut) kecil yang terdiri dari integer.
2. Anda dapat melakukan query RMinQ/RMaxQ/RSumQ dengan menyediakan dua indeks: kiri (L) dan kanan (R).
3. Anda dapat melakukan update pada range terentu dengan menyediakan sebuah indeks kiri (L), sebuah indeks kanan (R), dan NILAI (value) baru untuk range [L,R] ini. Kita menggunakan update seperlunya (lazy update) untuk mengoptimalkan performa.

5. Implementasi

Sayangnya, struktur data ini tidak ada dalam standard library C++,, Python, Java, ataupun OCaml untuk 2024. Maka, kita harus menulis implementasi kita sendiri.


Silahkan lihat pada contoh implementasi struktur data Pohon Segmen dalam C++/Python/Java/OCaml dengan prinsip Object-Oriented Programming (OOP): segmenttree_ds.cpp | py | java | ml


Anda bebas untuk memodifikasi implementasi ini sesuai dengan yang diperlukan.