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).
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
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.
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.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Buat
Query Range
Update Range