Segment Tree Basics and Visualization

Considering this is the first chapter, I do not intend to delve into the implementation details of the segment tree. The specific code will be introduced in the data structure design chapters later. However, you can get an intuitive sense of the variations of the segment tree with the help of a visualization panel.

Firstly, the basic segment tree includes the range query query and single-point modification update methods. You can open this visualization panel, click through the code line by line, and observe the execution process of the query and update methods:

You can see that the leaf nodes of this binary tree are the elements in the array, and the non-leaf nodes are the summary information of the index range (segment), which is the origin of the name "segment tree."

However, the segment tree above has a problem: it must be constructed with the nums array. If we want to perform range operations on a very long range, such as [0, 10^9], it would require $10^9$ space complexity to construct the segment tree, which is very wasteful.

The implementation of the dynamic segment tree uses the "dynamic opening" technique to optimize the memory overhead of the segment tree when handling sparse data. You can open this visualization panel, click through the code line by line, and observe the dynamic construction process of the segment tree:

The implementations above only support "single-point updates," but a more common requirement is range updates, such as updating all elements in the index range [i, j] to val. The implementation of the lazy update segment tree utilizes the "lazy update" technique to add rangeAdd/rangeUpdate methods to the segment tree, allowing any length of range updates to be completed in $O(\log N)$ time complexity.

You can open this visualization panel, click through the code line by line, and observe the operation process of the lazy update segment tree. Range updates require modifying only a few nodes:

Below, we introduce the application scenarios and core principles of the segment tree.

Application Scenarios

In Selection Sort, we will attempt to solve a requirement, which is to calculate the minimum value from index i to the end of the nums array.

We propose an optimization attempt using a suffixMin array, which precomputes a suffixMin array so that suffixMin[i] = min(nums[i..]), allowing the minimum value of nums[i..] to be queried in $O(1)$ time: