写在前面： 此博客内容已经同步到我的博客网站，如需要获得更优的阅读体验请前往https://blog.mainjay.cloudns.ch/blog/algorithm/segment-tree
1. 为什么需要线段树？
1.1 问题起源
想象这样一个场景：有一个长度为 n 的数组，我们需要经常进行以下操作：
- 查询数组中某个区间 [l,r] 的总和
- 修改数组中某个元素的值
- 修改数组中某个区间内所有元素的值
对于这类问题，我们有几种解决方案：
方案1：直接遍历
- 区间查询：O(n)
- 单点修改：O(1)
- 区间修改：O(n)
- 空间复杂度：O(1)
方案2：前缀和数组
- 区间查询：O(1)
- 单点修改：O(n)
- 区间修改：O(n)
- 空间复杂度：O(n)
方案3：线段树
- 区间查询：O(log n)
- 单点修改：O(log n)
- 区间修改：O(log n)
- 空间复杂度：O(n)
这就是为什么我们需要线段树 —— 它在查询和修改操作之间取得了很好的平衡。
1.2 线段树的本质
线段树本质上是一种将区间划分为多个小区间，并用树状结构管理这些区间的数据结构。每个节点代表一个区间，节点存储这个区间的某种统计信息（如和、最大值、最小值等）。
2. 线段树的设计思想
2.1 核心思想
- 区间划分：将大区间递归地划分为更小的区间，直到不能再分（区间长度为1）
- 信息聚合：父节点存储的信息是由其子节点的信息聚合而来
- 懒惰更新：当需要对一个大区间进行修改时，不立即修改所有子节点，而是先标记父节点，等到需要用到子节点时再更新
2.2 为什么这样设计是高效的？
-
二分思想：
- 查询时，如果当前区间完全包含在目标区间内，直接返回结果
- 如果部分重叠，则递归处理子区间
- 平均只需要访问 O(log n) 个节点
-
区间管理：
- 每个节点管理一个连续区间
- 父节点区间 = 左子节点区间 + 右子节点区间
- 这种设计使得区间操作变得高效
3. 线段树的应用场景
3.1 实际应用场景
-
游戏排行榜系统
- 问题：需要快速查询某个分数段内的玩家数量，同时支持玩家分数更新
- 为什么用线段树：可以O(log n)时间内完成区间查询和分数更新
-
文本编辑器
- 问题：需要支持区间插入、删除和查询操作
- 为什么用线段树：可以高效管理文本块，支持快速的区间操作
-
系统监控
- 问题：需要查询某时间段内的系统负载最大值/最小值
- 为什么用线段树：可以快速响应区间统计查询
-
地理信息系统
- 问题：需要查询某个矩形区域内的点数量
- 为什么用线段树：可以将二维问题转化为一维区间查询
3.2 算法题中的应用
-
区间统计类问题
- 例：查询区间内有多少个不同的数
- 例：查询区间内的众数
-
动态维护区间信息
- 例：维护区间最大连续子段和
- 例：维护区间GCD
4. 线段树的优化技巧
4.1 内存优化
-
动态开点
- 适用场景：区间范围很大但实际数据稀疏
- 实现方式：用map或指针动态分配节点
- 优势：大大减少内存使用
-
离散化
- 适用场景：数值范围很大但数据量较小
- 实现方式：将原始值映射到更小的范围
- 优势：减少树的大小，提高效率
4.2 性能优化
-
启发式合并
- 适用场景：需要合并两个线段树
- 实现方式：总是将小树合并到大树上
- 优势：减少合并操作的时间复杂度
-
位运算优化
- 计算父子节点关系时使用位运算
- 使用位运算优化区间操作
5. 线段树的扩展
5.1 二维线段树
- 处理矩形区域的查询和修改
- 时间复杂度：O(log n * log m)
- 空间复杂度：O(n * m)
5.2 可持久化线段树
- 支持查询历史版本
- 每次修改只需要O(log n)的额外空间
- 适用于需要维护历史信息的场景
6. 基本操作
6.1 完整的线段树实现
// SegmentTree 定义线段树结构
type SegmentTree struct {
tree []int64 // 存储线段树节点的数组
lazy []int64 // 懒惰标记数组
data []int64 // 原始数据数组
n int // 原始数组长度
merge func(int64, int64) int64 // 节点合并函数，可以是求和、最大值、最小值等
}
// NewSegmentTree 初始化线段树
// arr: 原始数组
// mergeFunc: 节点合并函数，定义如何合并两个子节点的信息
func NewSegmentTree(arr []int64, mergeFunc func(int64, int64) int64) *SegmentTree {
n := len(arr)
tree := make([]int64, 4*n) // 开4倍空间确保足够
lazy := make([]int64, 4*n)
data := make([]int64, n)
copy(data, arr)
st := &SegmentTree{
tree: tree,
lazy: lazy,
data: data,
n: n,
merge: mergeFunc,
}
// 构建线段树
st.buildTree(0, 0, n-1)
return st
}
// buildTree 构建线段树
// node: 当前节点在tree数组中的索引
// start, end: 当前节点表示的区间范围
func (st *SegmentTree) buildTree(node, start, end int) int64 {
// 叶子节点
if start == end {
st.tree[node] = st.data[start]
return st.tree[node]
}
// 递归构建左右子树
mid := start + (end-start)/2
leftNode := 2*node + 1
rightNode := 2*node + 2
leftSum := st.buildTree(leftNode, start, mid)
rightSum := st.buildTree(rightNode, mid+1, end)
// 合并子节点信息
st.tree[node] = st.merge(leftSum, rightSum)
return st.tree[node]
}
// pushDown 下推懒惰标记
func (st *SegmentTree) pushDown(node, start, end int) {
// 如果没有懒惰标记，直接返回
if st.lazy[node] == 0 {
return
}
// 计算左右子节点
leftNode := 2*node + 1
rightNode := 2*node + 2
mid := start + (end-start)/2
// 更新左子节点
st.tree[leftNode] += st.lazy[node] * int64(mid-start+1)
st.lazy[leftNode] += st.lazy[node]
// 更新右子节点
st.tree[rightNode] += st.lazy[node] * int64(end-mid)
st.lazy[rightNode] += st.lazy[node]
// 清除当前节点的懒惰标记
st.lazy[node] = 0
}
// QueryRange 查询区间[l,r]的信息
func (st *SegmentTree) QueryRange(l, r int) int64 {
if l < 0 || r >= st.n || l > r {
panic("Invalid range")
}
return st.queryRange(0, 0, st.n-1, l, r)
}
// queryRange 内部查询函数
func (st *SegmentTree) queryRange(node, start, end, l, r int) int64 {
// 如果当前区间完全在查询区间外
if start > r || end < l {
return 0 // 根据具体问题返回合适的默认值
}
// 如果当前区间完全在查询区间内
if l <= start && end <= r {
return st.tree[node]
}
// 处理懒惰标记
st.pushDown(node, start, end)
// 分别查询左右子区间
mid := start + (end-start)/2
leftNode := 2*node + 1
rightNode := 2*node + 2
leftSum := st.queryRange(leftNode, start, mid, l, r)
rightSum := st.queryRange(rightNode, mid+1, end, l, r)
return st.merge(leftSum, rightSum)
}
// UpdateRange 更新区间[l,r]中的值，增加val
func (st *SegmentTree) UpdateRange(l, r int, val int64) {
if l < 0 || r >= st.n || l > r {
panic("Invalid range")
}
st.updateRange(0, 0, st.n-1, l, r, val)
}
// updateRange 内部更新函数
func (st *SegmentTree) updateRange(node, start, end, l, r int, val int64) {
// 如果当前区间完全在更新区间外
if start > r || end < l {
return
}
// 如果当前区间完全在更新区间内
if l <= start && end <= r {
// 更新当前节点
st.tree[node] += val * int64(end-start+1)
// 如果不是叶子节点，添加懒惰标记
if start != end {
st.lazy[node] += val
}
return
}
// 处理懒惰标记
st.pushDown(node, start, end)
// 分别更新左右子区间
mid := start + (end-start)/2
leftNode := 2*node + 1
rightNode := 2*node + 2
st.updateRange(leftNode, start, mid, l, r, val)
st.updateRange(rightNode, mid+1, end, l, r, val)
// 更新当前节点
st.tree[node] = st.merge(st.tree[leftNode], st.tree[rightNode])
}
// 使用示例
func Example() {
// 创建一个支持区间求和的线段树
arr := []int64{1, 3, 5, 7, 9, 11}
st := NewSegmentTree(arr, func(a, b int64) int64 {
return a + b
})
// 查询区间和
sum := st.QueryRange(1, 3) // 查询区间[1,3]的和：3+5+7=15
// 更新区间
st.UpdateRange(1, 4, 2) // 将区间[1,4]中的每个数都加2
// 再次查询
newSum := st.QueryRange(1, 3) // 现在是(3+2)+(5+2)+(7+2)=21
}
6.2 其他常见操作的实现
// 查询区间最大值的线段树
func NewMaxSegmentTree(arr []int64) *SegmentTree {
return NewSegmentTree(arr, func(a, b int64) int64 {
if a > b {
return a
}
return b
})
}
// 查询区间最小值的线段树
func NewMinSegmentTree(arr []int64) *SegmentTree {
return NewSegmentTree(arr, func(a, b int64) int64 {
if a < b {
return a
}
return b
})
}
// 查询区间GCD的线段树
func NewGCDSegmentTree(arr []int64) *SegmentTree {
return NewSegmentTree(arr, func(a, b int64) int64 {
return gcd(a, b)
})
}
// 辅助函数：计算最大公约数
func gcd(a, b int64) int64 {
if b == 0 {
return a
}
return gcd(b, a%b)
}
7. 总结
线段树是一个强大的数据结构，特别适合处理区间查询和修改操作。虽然实现相对复杂，但在需要频繁进行区间操作的场景中，它的效率远超普通的数组操作。掌握线段树的原理和实现，对解决区间相关问题有很大帮助。
8. LeetCode 练习题
8.1 基础题目
-
- 难度：中等
- 特点：基础线段树的应用，实现单点修改和区间查询
- 知识点：线段树的基本操作
-
- 难度：简单
- 特点：可以用线段树解决，但前缀和是更优解
- 知识点：理解何时使用线段树
8.2 进阶题目
-
- 难度：困难
- 特点：需要离散化 + 线段树
- 知识点：离散化处理、动态统计
-
- 难度：困难
- 特点：前缀和 + 线段树
- 知识点：复合数据结构的应用
8.3 高级题目
-
- 难度：困难
- 特点：需要处理区间覆盖
- 知识点：懒惰标记的应用
-
- 难度：困难
- 特点：区间重叠计数
- 知识点：差分思想 + 线段树
8.4 扩展应用
-
- 难度：困难
- 特点：二维线段树 / 扫描线
- 知识点：线段树的二维应用
-
- 难度：困难
- 特点：线段树 + 分治
- 知识点：复杂区间查询
8.5 练习建议
-
循序渐进：
- 先从 307 题开始，掌握基本实现
- 然后尝试 315 题，学习离散化技巧
- 最后挑战 732、850 等高级题目
-
关注变化：
- 单点修改 vs 区间修改
- 区间查询的不同统计量
- 一维问题 vs 二维问题
-
优化思路：
- 考虑是否真的需要线段树
- 思考是否可以用其他数据结构
- 注意空间和时间的平衡