# Segment Tree Basics and Visualization

Prerequisite Knowledge

Before reading this article, you should first learn:

Summary in One Sentence

A Segment Tree is a derivative of the binary tree structure, used to efficiently solve range queries and dynamic modification problems. The time complexity for range queries is $O(\log N)$, and for dynamic modification of a single element, it is also $O(\log N)$.

The visual panel supports creating and using a segment tree. The panel below illustrates the logical structure, underlying array, and basic operations `query, update`

of a segment tree:

Considering this is the first chapter, I do not intend to delve deeply into the implementation details of segment trees. Instead, I aim to provide you with an understanding of the basic principles and application scenarios of segment trees, giving you an intuitive understanding of this data structure. Detailed code implementations are reserved for later sections on data structure design, following the binary tree exercises, making an in-depth discussion here unnecessary.

Let me begin with an optimization idea mentioned in Selection Sort, gradually introducing the principles of segment trees and explaining why we need such a data structure.

## Recap

In the previous article Selection Sort, I proposed an optimization attempt using a `suffixMin`

array. This involves precomputing a `suffixMin`

array such that `suffixMin[i] = min(nums[0..i])`

, allowing us to query the minimum value of `nums[0..i]`

in $O(1)$ time: