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. Specific codes will be introduced in the subsequent data structure design chapters. However, here you can use a visual panel to intuitively understand some variations of the segment tree.

Firstly, the basic segment tree includes interval query query and single point update update methods. You can open this visual panel, click the code step by step, 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 aggregated information of the index intervals (segments), which is where the name "segment tree" comes from.

However, this segment tree has a problem: it requires the nums array for construction. If we want to perform interval operations on a very long range, such as [0, 10^9], we would need $10^9$ space complexity to construct the segment tree, which is very wasteful.

The implementation of a dynamic segment tree uses the "dynamic node opening" technique to optimize the memory overhead of the segment tree for sparse data. You can open this visual panel, click the code step by step, and observe the dynamic construction process of the segment tree:

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

You can open this visual panel, click the code step by step, and observe the operation process of the lazy update segment tree. The rangeUpdate method does not need to immediately update all leaf nodes within the interval when updating an interval. Instead, it buffers the update value in a non-leaf node, and only propagates the update value to the leaf nodes gradually when the query method is called for interval queries:

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

Application Scenarios

In Selection Sort, we 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, i.e., precomputing a suffixMin array such that suffixMin[i] = min(nums[i..]), allowing the minimum value of nums[i..] to be queried in $O(1)$ time:

Core API of Segment Tree

Core Principle of Segment Tree

Why is the Tree Height O(log N)

Why is query O(logN)

Why update is O(logN)