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