从原理到实战带你认识线段树：基础篇

线段树是一种用于维护有序数组的区间更新和查询的数据结构。它通过递归地将每个区间分解为两个子区间，直到每个子区间只包含一个元素为止。在每个递归层级，线段树维护每个子区间的统计信息，以便能够高效地进行区间查询和更新。在本篇文章中，我们将从线段树的原理开始，逐步深入了解其工作机制，并通过代码实例来展示其实现和应用。

一、线段树的原理

线段树的核心思想是将一个区间[L,R]分解为两个子区间[L,M]和[M+1,R]，其中M=(L+R)/2。然后，对于每个子区间，递归地维护其统计信息。具体来说，对于一个节点表示的区间[L,R]，其左子树的节点表示区间[L,M]，右子树的节点表示区间[M+1,R]。每个节点维护了其表示区间的最小值、最大值、和等信息。

二、线段树的实现

下面我们将通过Python代码来展示线段树的实现。假设我们有一个有序数组arr，我们将使用线段树来维护这个数组的区间最小值。

首先，我们需要定义一个节点类来表示线段树的节点。每个节点包含一个表示区间的属性range和一个子节点列表children。children中的每个子节点都是一个线段树的节点，它们分别表示range的左右子区间。

class SegmentTreeNode:
    def __init__(self, range):
        self.range = range
        self.children = []
        self.min_val = float('inf')

接下来，我们可以定义一个函数来构建线段树。该函数将有序数组作为输入，并返回构建好的线段树的根节点。

def build_segment_tree(arr):
    def build(start, end):
        if start == end:
            return SegmentTreeNode(start)
        mid = (start + end) // 2
        left_child = build(start, mid)
        right_child = build(mid + 1, end)
        root = SegmentTreeNode(start, end)
        root.children = [left_child, right_child]
        root.min_val = min(left_child.min_val, right_child.min_val)
        return root
    return build(0, len(arr) - 1)

三、线段树的应用

现在我们已经实现了线段树，接下来我们将展示如何使用它来查询区间最小值。假设我们有一个线段树的根节点root，我们可以通过以下方式查询区间[L,R]的最小值：

1. 如果L小于root的左子节点的范围的最小值，则查询区间[L,R]的最小值等价于查询左子树的最小值。因此，我们递归地调用query函数来查询左子树的最小值。
2. 如果R大于root的右子节点的范围的最大值，则查询区间[L,R]的最小值等价于查询右子树的最小值。因此，我们递归地调用query函数来查询右子树的最小值。
3. 如果root的范围包含在区间[L,R]中，我们需要比较root节点的最小值和左右子树的最小值来确定区间[L,R]的最小值。如果root节点的最小值小于等于左右子树的最小值中的较小值，则区间[L,R]的最小值为root节点的最小值；否则，我们需要进一步递归地查询左右子树中较小值对应的子区间。
4. 如果以上情况都不满足，我们需要进一步递归地查询左右子树中较小值对应的子区间。通过比较左右子树的最小值来确定查询哪个子区间。如果左子树的最小值小于等于右子树的最小值，则查询左子树中较小值对应的子区间；否则，查询右子树中较小值对应的子区间。最后返回查询结果即可。
   ```python
   def query(root, L, R):
   if L < root.left_child.range[0] or R > root.right_child.range[1]:

    return float('inf') if L < root.left_child.range[0] else float('-inf') if R > root.right_child.range[1] else None

   if