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.
To toggle between the RMinQ/RMaxQ/RSumQ Segment Tree, select the respective header. Note that there can be other type of range queries than the three classics shown in this visualization.
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.
View the visualization of Segment Tree (tree on top of an array) here!
The tree on the top side shows the Segment Tree structure. The vertices are indexed in the same manner as with Binary Heap data structure where the root is at index 1 and the left/right child of a vertex p is 2*p/2*p+1, respectively. The value inside each vertex shows the MinIndex/MaxIndex/Sum value of the corresponding range/segment [L,R] of the underlying array A. We put "p:[L,R]" identifier in red color below each vertex except when L=R and that segment corresponds to a single array index (only that index is shown).
Vertices that are lazily updated will have this purple ring highlight. This lazy update technique will be explained in subsequent slides.
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.
The bottommost row shows the content of the underlying array A (yellow colored) from which the Segment Tree structure is built.
Each leaf vertex in the Segment Tree corresponds to an individual index in the corresponding array A. For Min ST and Max ST, the leaf vertex in the Segment Tree contains the index itself (the minimum/maximum element of a subarray with just one element is that element itself). For Sum ST, the leaf vertex in the Segment Tree contains the only value of that single-element subarray.
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.
There are three basic operations that are available in Segment Tree data structure visualization (for all 3 modes: RMinQ/RMaxQ/RSumQ):
- You can create RMinQ/RMaxQ/RSumQ Segment Tree from either a user-defined array of integers (maximum of 16 two-digits integer), or let the system provide a small random integer array or a small random but sorted integer array.
- You can do RMinQ/RMaxQ/RSumQ by specifying a left (L) and a right (R) indices.
- You can do Range Update by specifying a left (L) index, a right (R) index, and a new VALUE for this range [L,R]. We employ lazy update strategy for fast performance. You can still do Point Update (updating a single index only) by setting L = R.
For the details of these three operations, read CP4 or attend live CS3233 class.
Unfortunately, this data structure is not yet available in C++ STL, Python, Java API, or OCaml Standard Library as of 2024. Therefore, we have to write our own implementation.
Please look at the following C++/Python/Java/OCaml implementations of this Segment Tree data structure in Object-Oriented Programming (OOP) fashion: segmenttree_ds.cpp | py | java | ml
Again, you are free to customize this custom library implementation to suit your needs.
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.
Create
Range Query
Range Update