使用线段树实现区间求和

题目

使用线段树实现区间求和

信息

• 类型：问答
• 难度：⭐

考点

线段树基本概念,线段树构建,单点更新,区间查询

快速回答

线段树是一种用于高效处理区间查询的二叉树结构。本题要求实现：

• 构建线段树：递归地将数组划分为左右子树
• 单点更新：递归更新叶子节点并回溯更新父节点
• 区间查询：递归合并子区间的查询结果

核心公式：
父节点索引 = (当前索引 * 2) + 1（左子节点）
父节点索引 = (当前索引 * 2) + 2（右子节点）

解析

原理说明

线段树是一种二叉树结构，每个节点存储一个区间的聚合信息（如区间和）。对于长度为 n 的数组：

• 叶子节点：存储单个元素值
• 非叶子节点：存储子区间的合并值（如左右子节点之和）
• 树高度：O(log n)，支持 O(log n) 的更新和查询

代码示例（Python）

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 4 * self.n  # 保守估计空间
        self.tree = [0] * self.size
        self._build(data, 0, 0, self.n-1)

    # 构建线段树
    def _build(self, data, idx, left, right):
        if left == right:
            self.tree[idx] = data[left]
            return
        mid = (left + right) // 2
        self._build(data, 2*idx+1, left, mid)    # 左子树
        self._build(data, 2*idx+2, mid+1, right) # 右子树
        self.tree[idx] = self.tree[2*idx+1] + self.tree[2*idx+2]

    # 单点更新
    def update(self, pos, value, idx=0, left=0, right=None):
        if right is None: right = self.n-1
        if left == right:
            self.tree[idx] = value
            return
        mid = (left + right) // 2
        if pos <= mid:
            self.update(pos, value, 2*idx+1, left, mid)
        else:
            self.update(pos, value, 2*idx+2, mid+1, right)
        self.tree[idx] = self.tree[2*idx+1] + self.tree[2*idx+2]

    # 区间查询
    def query(self, ql, qr, idx=0, left=0, right=None):
        if right is None: right = self.n-1
        if qr < left or ql > right:  # 区间无重叠
            return 0
        if ql <= left and qr >= right:  # 完全包含
            return self.tree[idx]
        mid = (left + right) // 2
        left_sum = self.query(ql, qr, 2*idx+1, left, mid)
        right_sum = self.query(ql, qr, 2*idx+2, mid+1, right)
        return left_sum + right_sum

# 使用示例
arr = [1, 3, 5, 7, 9]
sg_tree = SegmentTree(arr)
print(sg_tree.query(1, 3))  # 输出 15 (3+5+7)
sg_tree.update(2, 10)       # 将位置2的元素更新为10
print(sg_tree.query(1, 3))  # 输出 20 (3+10+7)

最佳实践

• 空间分配：使用 4*n 的保守空间避免溢出
• 递归终止条件：区间长度为1时到达叶子节点
• 区间划分：使用 mid = (left + right) // 2 保证平衡
• 查询优化：当当前区间完全包含在查询区间时直接返回

常见错误

• 索引错误：混淆左右子树索引（左：2*i+1，右：2*i+2）
• 区间不匹配：构建/查询时未正确传递 [left, right] 边界
• 更新遗漏：修改叶子节点后未回溯更新父节点
• 空间不足：数组开太小导致越界（最小需 4*n 空间）

扩展知识

• 变种应用：区间最小值（Min Segment Tree）、区间最大值
• 惰性传播：高效处理区间更新的延迟更新技术
• 动态线段树：支持动态插入/删除元素
• 替代结构：树状数组（Binary Indexed Tree）在单点更新+区间求和场景更简洁