线段树原理与区间查询应用

# 1. 线段树简介**

线段树是一种树形数据结构，常用于解决区间查询和更新问题。它由一个根节点和多个子节点组成，每个节点代表一个区间。线段树的主要目的是将一个数组或序列中的元素组织成一棵树，以便快速高效地查询和更新区间信息。

线段树的优势在于它可以将区间查询和更新操作的时间复杂度降低到 O(log n)，其中 n 是数组或序列的长度。与其他数据结构（如平衡树）相比，线段树在处理大规模数据时具有更优越的性能。

# 2. 线段树的构建

### 2.1 节点的表示和范围

线段树的每个节点代表一个区间，区间范围由该节点的左右端点 `l` 和 `r` 确定。根节点的区间范围覆盖整个数组，即 `[1, n]`。对于每个非叶节点，其左右子节点分别代表其区间的左半部分和右半部分，即：

- 左子节点的区间范围：`[l, mid]`，其中 `mid = (l + r) / 2`
- 右子节点的区间范围：`[mid + 1, r]`

### 2.2 递归构建线段树

线段树的构建采用自顶向下的递归算法。给定一个数组 `nums` 和其长度 `n`，构建过程如下：

def build_segment_tree(nums, l, r):
    """
    构建线段树

    参数：
        nums：原始数组
        l：左端点
        r：右端点

    返回：
        根节点
    """
    if l > r:
        return None

    # 创建根节点
    root = TreeNode()

    # 如果区间只有一个元素，则该元素为根节点的值
    if l == r:
        root.val = nums[l]
        return root

    # 计算中点
    mid = (l + r) // 2

    # 递归构建左子树
    root.left = build_segment_tree(nums, l, mid)

    # 递归构建右子树
    root.right = build_segment_tree(nums, mid + 1, r)

    # 根节点的值为左右子树值的和
    root.val = root.left.val + root.right.val

    return root

**代码逻辑逐行解读：**

1. 如果区间无效（`l > r`），返回 `None`。
2. 创建根节点 `root`。
3. 如果区间只有一个元素，将该元素赋值给 `root.val` 并返回 `root`。
4. 计算区间中点 `mid`。
5. 递归构建左子树，并将左子树根节点赋值给 `root.left`。
6. 递归构建右子树，并将右子树根节点赋值给 `root.right`。
7. 将根节点的值设为左右子树值的和。
8. 返回根节点 `root`。

**参数说明：**

- `nums`：原始数组
- `l`：左端点
- `r`：右端点

**返回：**

- 根节点

# 3.1 区间查询的基本原理

线段树的查询操作是基于分治思想，将查询区间划分为左右两个子区间，然后递归地查询这两个子区间。具体步骤如下：

1. **判断查询区间是否与当前节点区间相交：**如果查询区间与当前节点区间不相交，则直接返回空值。
2. **判断查询区间是否完全包含当前节点区间：**如果查询区间完全包含当前节点区间，则直接返回当前节点的值。
3. **递归查询左右子区间：**如果查询区间与当前节点区间部分相交，则递归地查询左右子区间，并将查询结果合并返回。

### 3.2 递归查询区间和

以查询区间和为例，递归查询区间和的算法如下：

def query_sum(self, left, right):
    """
    查询指定区间[left, right]的和。

    Args:
        left (int): 查询区间的左端点。
        right (int): 查询区间的右端点。

    Returns:
        int: 查询区间的和。
    """

    # 判断查询区间是否与当前节点区间相交
    if not self.is_intersect(left, right):
        return 0

    # 判断查询区间是否完全包含当前节点区间
    if self.is_contain(left, right):
        return self.val

    # 递归查询左右子区间
    left_sum = self.left_child.query_sum(left, right)
    right_sum = self.right_child.query_sum(left, right)

    # 返回查询结果
    return left_sum + right_sum

**代码逻辑分析：**

* 函数`query_sum`接收两个参数`left`和`right`，表示查询区间的左右端点。
* 首先判断查询区间是否与当前节点区间相交，如果不相交则返回0。
* 然后判断查询区间是否完全包含当前节点区间，如果包含则返回当前节点的值。
* 如果查询区间与当前节点区间部分相交，则递归查询左右子区间，并将查询结果合并返回。

### 3.3 递归查询区间最大值

类似地，递归查询区间最大值的算法如下：

def query_max(self, left, right):
    """
    查询指定区间[left, right]的最大值。

    Args:
        left (int): 查询区间的左端点。
        right (int): 查询区间的右端点。

    Returns:
        int: 查询区间的最大值。
    """

    # 判断查询区间是否与当前节点区间相交
    if not self.is_intersect(left, right):
        return -inf

    # 判断查询区间是否完全包含当前节点区间
    if self.is_contain(left, right):
        return self.val

    # 递归查询左右子区间
    left_max = self.left_child.query_max(left, right)
    right_max = self.right_child.query_max(left, right)

    # 返回查询结果
    return max(left_max, right_max)

**代码逻辑分析：**