Pohon Segmen

1. Introduction

Sebuah pohon segmen (Segment Tree / ST) adalah pohon biner yang dibuat berdasarkan sebuah array (biasanya integer) supaya kita dapat menyelesaikan query Range Min/Max/Sum serta query Range 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 O(N).

2. Mode

Untuk berpindah antara Pohon Segmen RMinQ/RMaxQ/RSumQ, pilihlah header yang sesuai.

3. Visualisasi

Lihatlah visualisasi dari Pohon Segmen di sini!
Bagian atas menunjukkan struktur Pohon Segmen di mana setiap simpulnya menunjukkan nilai Min/Max/Sum (jumlah) dari range yang bersangkutan (berwarna merah dengan format [L,R]).
Baris bawah menunjukkan nilai awal array A (berwarna kuning) yang digunakan untuk membuat Pohon Segmen.
Simpul-simpul yang di-update seperlunya (lazy update) akan memiliki highlight cincin ungu.
Tiap simpul yang berupa daun (leaf) dari Pohon Segmen ini melambangkan indeks di array A yang bersangkutan.

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. Implementation

Unfortunately, this data structure is not yet available in C++ STL, Java API, Python or OCaml Standard Library as of 2020. Therefore, we have to write our own implementation.


Please look at the following C++/Java/Python/OCaml implementations of this Segment Tree data structure in Object-Oriented Programming (OOP) fashion:
segmenttree_ds.cpp
segmenttree_ds.java
segmenttree_ds.py
segmenttree_ds.ml


Again, you are free to customize this custom library implementation to suit your needs.