本文详细介绍了线段树的基本概念和应用场景，包括区间查询和更新操作。文章还深入探讨了线段树的数据结构和构建方法，并提供了具体的实现代码示例。通过阅读本文，读者可以全面了解线段树入门的相关知识。

线段树是一种高效的数据结构，用于处理区间查询和区间修改的问题。在线段树中，每个节点都存储了一个区间的信息，通过递归分解整个区间，可以实现高效的区间查询和修改操作。

线段树的基本概念

线段树的每个节点代表一个区间，可以通过递归的方式将区间分解成更小的子区间。每个非叶节点表示一个区间，其左右子节点分别表示该区间的左右子区间。例如，考虑一个长度为5的数组，使用线段树表示其区间时，根节点表示整个区间[0, 4]，左子节点表示区间[0, 2]，右子节点表示区间[3, 4]，继续递归划分，直到到达叶节点。

线段树的应用场景

线段树通常应用于以下场景：

1. 区间求和：查询某个区间内所有元素的和。
2. 区间最大值/最小值：查询某个区间内的最大值或最小值。
3. 区间更新：更新某个区间内所有元素的值。
4. 区间逆序对：计算区间内的逆序对数量。

线段树的数据结构可以采用数组或链表。数组表示的线段树更适用于静态区间查询和更新，链表表示的线段树则更适合动态区间维护。

线段树的节点结构

一个线段树节点通常包含以下信息：

• 区间范围：表示节点对应的区间范围。
• 区间值：表示节点对应的区间范围内的值，例如区间和或区间最大值。
• 左子节点：指向表示左子区间的子节点。
• 右子节点：指向表示右子区间的子节点。

示例代码展示了如何定义一个线段树节点结构：

class SegmentTreeNode:
    def __init__(self, start, end, value=None):
        self.start = start
        self.end = end
        self.value = value
        self.left = None
        self.right = None

线段树的树形结构

线段树的树形结构可以表示为一个二叉树，每个节点表示一个区间。构造线段树时，根节点表示整个区间，然后递归地分裂成左右子节点，直到叶子节点表示单个元素。

示例代码展示了如何构建一个简单的线段树树形结构：

def build_segment_tree_util(arr, start, end, pos, segment_tree):
    if start == end:
        segment_tree[pos] = SegmentTreeNode(start, end, arr[start])
    else:
        mid = (start + end) // 2
        segment_tree[pos] = SegmentTreeNode(start, end)
        build_segment_tree_util(arr, start, mid, 2 * pos + 1, segment_tree)
        build_segment_tree_util(arr, mid + 1, end, 2 * pos + 2, segment_tree)
        segment_tree[pos].value = segment_tree[2 * pos + 1].value + segment_tree[2 * pos + 2].value

# 示例代码
arr = [1, 3, 5, 7, 9]
segment_tree = [None] * 21  # 容量为21的数组，足够存储长度为5的线段树
build_segment_tree_util(arr, 0, len(arr) - 1, 0, segment_tree)
print("Root Node:", segment_tree[0].value)  # 打印根节点的值

线段树的构建可以通过递归或非递归的方式实现。

线段树的递归构建

递归构建时，从根节点开始，根据区间范围递归创建左右子节点，直到叶子节点。

示例代码展示了如何递归构建线段树：

def build_segment_tree(arr, start, end):
    if start > end:
        return None

    node = SegmentTreeNode(start, end)

    if start == end:
        node.value = arr[start]
    else:
        mid = (start + end) // 2
        node.left = build_segment_tree(arr, start, mid)
        node.right = build_segment_tree(arr, mid + 1, end)
        node.value = node.left.value + node.right.value

    return node

线段树的非递归构建

非递归构建时，通过层次遍历的方式构建线段树，从叶子节点向上构建每个父节点。

def build_segment_tree(arr):
    n = len(arr)
    height = math.ceil(math.log2(n))
    tree_size = 2 * (1 << height) - 1
    segment_tree = [None] * tree_size

    build_segment_tree_util(arr, 0, n - 1, 0, segment_tree)
    return segment_tree

def build_segment_tree_util(arr, start, end, pos, segment_tree):
    if start == end:
        segment_tree[pos] = SegmentTreeNode(start, end, arr[start])
    else:
        mid = (start + end) // 2
        segment_tree[pos] = SegmentTreeNode(start, end)
        build_segment_tree_util(arr, start, mid, 2 * pos + 1, segment_tree)
        build_segment_tree_util(arr, mid + 1, end, 2 * pos + 2, segment_tree)
        segment_tree[pos].value = segment_tree[2 * pos + 1].value + segment_tree[2 * pos + 2].value

线段树支持两种基本操作：查询操作和更新操作。

查询操作

查询操作用于获取某个区间内的值，例如求和、最大值或最小值。查询操作通常自顶向下进行，根据查询区间范围，递归地向下搜索，直到找到子节点表示的区间完全包含查询区间。

示例代码展示了如何查询线段树中的区间和：

def query_segment_tree(node, start, end):
    if start > node.end or end < node.start:
        return 0
    if start <= node.start and end >= node.end:
        return node.value

    mid = (node.start + node.end) // 2
    left_sum = query_segment_tree(node.left, start, mid)
    right_sum = query_segment_tree(node.right, mid + 1, end)
    return left_sum + right_sum

更新操作

更新操作用于更新某个区间内的值。更新操作通常自底向上进行，递归地更新区间内的节点值，直到更新到根节点。

示例代码展示了如何更新线段树中的区间值：

def update_segment_tree(node, index, value):
    if node.start == node.end:
        node.value = value
        return
    mid = (node.start + node.end) // 2
    if index <= mid:
        update_segment_tree(node.left, index, value)
    else:
        update_segment_tree(node.right, index, value)
    node.value = node.left.value + node.right.value

时间复杂度

线段树的查询和更新操作的时间复杂度均为 O(log n)，其中 n 是数组的长度。这是因为每次查询或更新操作都会从根节点递归地访问到叶节点，高度为 log n 的树。

空间复杂度

线段树的空间复杂度为 O(n)，其中 n 是数组的长度。最坏情况下，线段树的节点数量为 2n-1，因此空间复杂度为 O(n)。

典型问题解析

区间求和

区间求和是线段树最常见的一种应用，用于查询某个区间内的元素和。

区间最大值/最小值

区间最大值或最小值用于查询某个区间内的最大值或最小值。

区间更新

区间更新用于更新某个区间内的所有元素，例如将区间内的所有元素加上一个固定值。

实战代码示例

这里提供一个完整的线段树实现，包括构建、查询和更新操作。

class SegmentTreeNode:
    def __init__(self, start, end, value=None):
        self.start = start
        self.end = end
        self.value = value
        self.left = None
        self.right = None

def build_segment_tree(arr):
    n = len(arr)
    height = math.ceil(math.log2(n))
    tree_size = 2 * (1 << height) - 1
    segment_tree = [None] * tree_size

    build_segment_tree_util(arr, 0, n - 1, 0, segment_tree)
    return segment_tree

def build_segment_tree_util(arr, start, end, pos, segment_tree):
    if start == end:
        segment_tree[pos] = SegmentTreeNode(start, end, arr[start])
    else:
        mid = (start + end) // 2
        segment_tree[pos] = SegmentTreeNode(start, end)
        build_segment_tree_util(arr, start, mid, 2 * pos + 1, segment_tree)
        build_segment_tree_util(arr, mid + 1, end, 2 * pos + 2, segment_tree)
        segment_tree[pos].value = segment_tree[2 * pos + 1].value + segment_tree[2 * pos + 2].value

def query_segment_tree(segment_tree, start, end, pos, query_start, query_end):
    if start > query_end or end < query_start:
        return 0
    if start >= query_start and end <= query_end:
        return segment_tree[pos].value

    mid = (start + end) // 2
    left_sum = query_segment_tree(segment_tree, start, mid, 2 * pos + 1, query_start, query_end)
    right_sum = query_segment_tree(segment_tree, mid + 1, end, 2 * pos + 2, query_start, query_end)
    return left_sum + right_sum

def update_segment_tree(segment_tree, index, value, pos, start, end):
    if start == end:
        segment_tree[pos].value = value
        return
    mid = (start + end) // 2
    if index <= mid:
        update_segment_tree(segment_tree, index, value, 2 * pos + 1, start, mid)
    else:
        update_segment_tree(segment_tree, index, value, 2 * pos + 2, mid + 1, end)
    segment_tree[pos].value = segment_tree[2 * pos + 1].value + segment_tree[2 * pos + 2].value

# 示例代码
arr = [1, 3, 5, 7, 9]
segment_tree = build_segment_tree(arr)
print(query_segment_tree(segment_tree, 0, 4, 0, 1, 3))  # 查询区间 [1, 3] 的和
print(update_segment_tree(segment_tree, 2, 10, 0, 0, 4))  # 将索引为 2 的元素更新为 10
print(query_segment_tree(segment_tree, 0, 4, 0, 1, 3))  # 再次查询区间 [1, 3] 的和

# 区间最大值/最小值查询
def query_max_segment_tree(segment_tree, pos, start, end, query_start, query_end):
    if start > query_end or end < query_start:
        return float('-inf')
    if start >= query_start and end <= query_end:
        return segment_tree[pos].value

    mid = (start + end) // 2
    left_max = query_max_segment_tree(segment_tree, 2 * pos + 1, start, mid, query_start, query_end)
    right_max = query_max_segment_tree(segment_tree, 2 * pos + 2, mid + 1, end, query_start, query_end)
    return max(left_max, right_max)

# 区间更新操作
def update_segment_tree(segment_tree, index, value, pos, start, end):
    if start == end:
        segment_tree[pos].value = value
        return
    mid = (start + end) // 2
    if index <= mid:
        update_segment_tree(segment_tree, index, value, 2 * pos + 1, start, mid)
    else:
        update_segment_tree(segment_tree, index, value, 2 * pos + 2, mid + 1, end)
    segment_tree[pos].value = segment_tree[2 * pos + 1].value + segment_tree[2 * pos + 2].value

# 示例代码
print(query_max_segment_tree(segment_tree, 0, 0, 4, 1, 3))  # 查询区间 [1, 3] 的最大值
print(update_segment_tree(segment_tree, 2, 10, 0, 0, 4))  # 将索引为 2 的元素更新为 10
print(query_max_segment_tree(segment_tree, 0, 0, 4, 1, 3))  # 再次查询区间 [1, 3] 的最大值