Segment Tree Basics and Visualization
Prerequisite Knowledge
Before reading this article, you need to first learn:
Summary in One Sentence
A segment tree is a derivative of the binary tree structure, used to efficiently solve interval queries and dynamic modifications. The time complexity for interval queries is , and for dynamically modifying a single element is .
The visualization panel supports the creation and use of segment trees. The panel below shows the logical structure of a segment tree, the underlying array, and basic operations query, update. You can click through the code line by line to observe changes in the tree structure:
The visualization panel should help you intuitively understand the origin of the name "segment tree": the leaf nodes of this binary tree are elements in the array, and the non-leaf nodes summarize the information of the index intervals (segments).
Considering this is the first chapter, I do not intend to delve deeply into the implementation details of segment trees. Instead, I aim to give you an understanding of the basic principles and application scenarios of segment trees, providing a clear concept of them. The code implementation and application of segment trees are arranged in the later chapter on data structure design, so there is no need to go deep here.
Let me start with an optimization idea mentioned in Selection Sort, gradually introducing the principles of segment trees and why we need such a data structure.
Previous Review
In the previous article Selection Sort, we had a requirement to compute the minimum value from index i to the end of the nums array.
At that time, we proposed an optimization attempt using a suffixMin array, which precomputes a suffixMin array such that suffixMin[i] = min(nums[i..]). This allows querying the minimum value of nums[i..] in time: