数据结构之线段树（Segment Tree）
线段树（Segment Tree）详解
1. 引言
线段树是一种二叉树数据结构，用于存储区间或线段的信息。它支持高效的区间查询和更新操作，特别适用于需要频繁对数组区间进行操作的场景。线段树在算法竞赛、数据库系统、地理信息系统等领域有广泛应用。
2. 基本概念
2.1 定义
线段树是一种平衡二叉树，其中每个节点代表一个区间。对于数组A[0...n-1]，线段树的根节点代表整个区间[0, n-1]，每个叶子节点代表数组中的一个元素，非叶子节点代表其子节点区间的并集。
2.2 特点
- 平衡性：线段树是一棵近似平衡的二叉树，高度为
O(log n) - 区间表示：每个节点存储一个区间的信息
- 递归结构：通过递归方式构建和查询
- 高效操作：支持
O(log n)时间复杂度的区间查询和更新
3. 数据结构设计
3.1 节点结构
classSegmentTreeNode:def__init__(self,start,end):self.start=start# 区间起始位置self.end=end# 区间结束位置self.mid=(start+end)//2# 区间中点self.left=None# 左子节点self.right=None# 右子节点self.value=0# 节点存储的值（如区间和、最小值等）self.lazy=0# 懒惰标记（用于延迟更新）3.2 树的构建
线段树可以通过递归方式构建：
defbuild_segment_tree(arr,start,end):ifstart==end:node=SegmentTreeNode(start,end)node.value=arr[start]returnnode node=SegmentTreeNode(start,end)mid=(start+end)//2node.left=build_segment_tree(arr,start,mid)node.right=build_segment_tree(arr,mid+1,end)node.value=node.left.value+node.right.value# 根据需求合并子节点值returnnode4. 核心操作
4.1 区间查询
线段树支持多种查询操作，如区间和、区间最小值、区间最大值等。
defquery(node,start,end):ifnode.start==startandnode.end==end:returnnode.value mid=node.midifend<=mid:returnquery(node.left,start,end)elifstart>mid:returnquery(node.right,start,end)else:left_val=query(node.left,start,mid)right_val=query(node.right,mid+1,end)returnleft_val+right_val# 根据需求合并结果4.2 单点更新
defupdate(node,index,value):ifnode.start==node.end:node.value=valuereturnmid=node.midifindex<=mid:update(node.left,index,value)else:update(node.right,index,value)node.value=node.left.value+node.right.value# 更新父节点值4.3 区间更新（带懒惰标记）
defrange_update(node,start,end,value):ifnode.start==startandnode.end==end:node.value+=(end-start+1)*value node.lazy+=valuereturnpush_down(node)# 下推懒惰标记mid=node.midifend<=mid:range_update(node.left,start,end,value)elifstart>mid:range_update(node.right,start,end,value)else:range_update(node.left,start,mid,value)range_update(node.right,mid+1,end,value)node.value=node.left.value+node.right.value4.4 懒惰标记下推
defpush_down(node):ifnode.lazy!=0:node.left.lazy+=node.lazy node.right.lazy+=node.lazy node.left.value+=node.lazy*(node.left.end-node.left.start+1)node.right.value+=node.lazy*(node.right.end-node.right.start+1)node.lazy=05. 时间复杂度分析
| 操作 | 时间复杂度 |
|---|---|
| 构建树 | O(n) |
| 区间查询 | O(log n) |
| 单点更新 | O(log n) |
| 区间更新 | O(log n) |
6. 应用场景
6.1 典型应用
- 区间和查询：计算数组中任意区间的元素和
- 区间最值查询：查找区间内的最大值或最小值
- 区间更新：对整个区间进行增量更新
- 动态数组操作：支持频繁的插入、删除和查询
6.2 实际应用
- 数据库索引：加速范围查询
- 地理信息系统：空间数据查询
- 图像处理：区域统计和变换
- 股票市场分析：时间序列数据查询
7. 代码实现（Python）
classSegmentTree:def__init__(self,data):self.n=len(data)self.tree=[0]*(4*self.n)self.build(data,0,0,self.n-1)defbuild(self,data,node,start,end):ifstart==end:self.tree[node]=data[start]returnmid=(start+end)//2self.build(data,2*node+1,start,mid)self.build(data,2*node+2,mid+1,end)self.tree[node]=self.tree[2*node+1]+self.tree[2*node+2]defquery(self,node,start,end,l,r):ifr<startorl>end:return0ifl<=startandend<=r:returnself.tree[node]mid=(start+end)//2left_sum=self.query(2*node+1,start,mid,l,r)right_sum=self.query(2*node+2,mid+1,end,l,r)returnleft_sum+right_sumdefupdate(self,node,start,end,index,value):ifstart==end:self.tree[node]=valuereturnmid=(start+end)//2ifindex<=mid:self.update(2*node+1,start,mid,index,value)else:self.update(2*node+2,mid+1,end,index,value)self.tree[node]=self.tree[2*node+1]+self.tree[2*node+2]defrange_query(self,l,r):returnself.query(0,0,self.n-1,l,r)defpoint_update(self,index,value):self.update(0,0,self.n-1,index,value)8. 扩展变种
8.1 线段树数组实现
使用数组实现线段树，避免递归开销：
classSegmentTreeArray:def__init__(self,data):self.n=len(data)self.tree=[0]*(4*self.n)self.build(data,0,0,self.n-1)# ... 其他方法与上述类似8.2 动态线段树
支持动态插入和删除操作的线段树：
classDynamicSegmentTree:def__init__(self):self.root=Nonedefinsert(self,value):# 动态插入节点passdefquery(self,l,r):# 查询区间pass9. 与其他数据结构的比较
9.1 与树状数组（Binary Indexed Tree）比较
| 特性 | 线段树 | 树状数组 |
|---|---|---|
| 空间复杂度 | O(n) | O(n) |
| 单点更新 | O(log n) | O(log n) |
| 区间查询 | O(log n) | O(log n) |
| 区间更新 | O(log n) | 不直接支持 |
| 构建时间 | O(n) | O(n) |
| 功能灵活性 | 高 | 低 |
9.2 与平衡二叉搜索树比较
- 线段树：专门为区间操作优化
- 平衡二叉搜索树：通用目的，支持点操作和范围查询
10. 优化技巧
10.1 懒惰标记
延迟更新操作，减少不必要的计算：
defrange_update_optimized(self,node,start,end,l,r,value):ifl<=startandend<=r:self.tree[node]+=(end-start+1)*value self.lazy[node]+=valuereturnself.push_down(node)mid=(start+end)//2ifl<=mid:self.range_update_optimized(2*node+1,start,mid,l,r,value)ifr>mid:self.range_update_optimized(2*node+2,mid+1,end,l,r,value)self.tree[node]=self.tree[2*node+1]+self.tree[2*node+2]10.2 内存优化
- 使用数组实现而非对象
- 按需分配节点
- 压缩存储
11. 实际案例
11.1 区间和查询
# 示例：计算数组 [1, 3, 5, 7, 9, 11] 中区间 [1, 4] 的和data=[1,3,5,7,9,11]st=SegmentTree(data)result=st.range_query(1,4)# 结果为 3 + 5 + 7 + 9 = 2411.2 区间更新
# 对区间 [1, 3] 的每个元素加 2st.range_update(1,3,2)# 查询更新后的区间和result=st.range_query(1,3)# 结果为 (3+2) + (5+2) + (7+2) = 2112. 总结
线段树是一种强大而灵活的数据结构，特别适用于需要频繁进行区间操作的场景。它的主要优势在于：
- 高效性：支持
O(log n)时间复杂度的区间查询和更新 - 灵活性：可以存储各种区间信息（和、最值、计数等）
- 可扩展性：支持多种扩展和优化
虽然实现相对复杂，但掌握线段树对于解决算法问题和系统设计都具有重要意义。