线段树（Segment Tree）

一句话说明

线段树就是把区间递归切开，每个节点维护一个区间答案，所以它擅长“动态区间查询 + 动态区间修改”。

先抓住它和树状数组的本质区别

树状数组更像“前缀信息压缩存储”。
线段树更像“把整个区间递归拆成一棵树”。

所以线段树的优势不是更短，而是更灵活：

• 可以维护区间和
• 可以维护区间最小值 / 最大值
• 可以维护区间最大子段和
• 可以支持区间加、区间赋值、区间翻转等延迟更新

代价就是代码更长，细节更多。

你要先记住节点含义

每个节点维护一个闭区间 [l, r] 的答案。

nums = [1, 3, 5, 7, 9, 11]
 
根节点负责 [0, 5]
左孩子负责 [0, 2]
右孩子负责 [3, 5]

如果我们维护的是区间和，那么父节点的值就是：

sum[l..r] = sum[left child] + sum[right child]

这就是线段树最核心的合并逻辑。

写线段树时脑子里要有这三件事

• 当前节点负责哪个区间
• 这个区间保存什么信息
• 左右子区间合并后，怎么得到当前区间答案

只要这三件事清楚，很多线段树题其实只是“换一个维护信息”。

Go 代码：区间和 + 单点修改

type SegmentTree struct {
    n    int
    tree []int
}
 
func NewSegmentTree(nums []int) *SegmentTree {
    st := &SegmentTree{
        n:    len(nums),
        tree: make([]int, 4*len(nums)),
    }
    if len(nums) > 0 {
        st.build(1, 0, len(nums)-1, nums)
    }
    return st
}
 
func (st *SegmentTree) build(node, left, right int, nums []int) {
    if left == right {
        st.tree[node] = nums[left]
        return
    }
 
    mid := left + (right-left)/2
    st.build(node*2, left, mid, nums)
    st.build(node*2+1, mid+1, right, nums)
    st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
 
func (st *SegmentTree) Update(index, val int) {
    st.update(1, 0, st.n-1, index, val)
}
 
func (st *SegmentTree) update(node, left, right, index, val int) {
    if left == right {
        st.tree[node] = val
        return
    }
 
    mid := left + (right-left)/2
    if index <= mid {
        st.update(node*2, left, mid, index, val)
    } else {
        st.update(node*2+1, mid+1, right, index, val)
    }
 
    st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
 
func (st *SegmentTree) Query(queryLeft, queryRight int) int {
    return st.query(1, 0, st.n-1, queryLeft, queryRight)
}
 
func (st *SegmentTree) query(node, left, right, queryLeft, queryRight int) int {
    if queryLeft <= left && right <= queryRight {
        return st.tree[node]
    }
 
    mid := left + (right-left)/2
    sum := 0
 
    if queryLeft <= mid {
        sum += st.query(node*2, left, mid, queryLeft, queryRight)
    }
    if queryRight > mid {
        sum += st.query(node*2+1, mid+1, right, queryLeft, queryRight)
    }
    return sum
}

什么时候需要懒标记

如果只是单点修改，不需要 lazy。
一旦题目变成：

• 区间 [l, r] 整段加上 delta
• 区间 [l, r] 整段赋值为 x

你就不能每次真的一路更新到底，否则复杂度会炸。
这时要用懒标记，把“这段区间还没下发的更新”先挂在当前节点上。

Go 代码：区间加 + 区间和

type LazySegmentTree struct {
    n    int
    tree []int
    lazy []int
}
 
func NewLazySegmentTree(nums []int) *LazySegmentTree {
    st := &LazySegmentTree{
        n:    len(nums),
        tree: make([]int, 4*len(nums)),
        lazy: make([]int, 4*len(nums)),
    }
    if len(nums) > 0 {
        st.build(1, 0, len(nums)-1, nums)
    }
    return st
}
 
func (st *LazySegmentTree) build(node, left, right int, nums []int) {
    if left == right {
        st.tree[node] = nums[left]
        return
    }
 
    mid := left + (right-left)/2
    st.build(node*2, left, mid, nums)
    st.build(node*2+1, mid+1, right, nums)
    st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
 
func (st *LazySegmentTree) pushDown(node, left, right int) {
    if st.lazy[node] == 0 || left == right {
        return
    }
 
    mid := left + (right-left)/2
    leftNode, rightNode := node*2, node*2+1
    add := st.lazy[node]
 
    st.tree[leftNode] += add * (mid - left + 1)
    st.tree[rightNode] += add * (right - mid)
    st.lazy[leftNode] += add
    st.lazy[rightNode] += add
    st.lazy[node] = 0
}
 
func (st *LazySegmentTree) AddRange(queryLeft, queryRight, delta int) {
    st.addRange(1, 0, st.n-1, queryLeft, queryRight, delta)
}
 
func (st *LazySegmentTree) addRange(node, left, right, queryLeft, queryRight, delta int) {
    if queryLeft <= left && right <= queryRight {
        st.tree[node] += delta * (right - left + 1)
        st.lazy[node] += delta
        return
    }
 
    st.pushDown(node, left, right)
    mid := left + (right-left)/2
 
    if queryLeft <= mid {
        st.addRange(node*2, left, mid, queryLeft, queryRight, delta)
    }
    if queryRight > mid {
        st.addRange(node*2+1, mid+1, right, queryLeft, queryRight, delta)
    }
 
    st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
 
func (st *LazySegmentTree) Query(queryLeft, queryRight int) int {
    return st.query(1, 0, st.n-1, queryLeft, queryRight)
}
 
func (st *LazySegmentTree) query(node, left, right, queryLeft, queryRight int) int {
    if queryLeft <= left && right <= queryRight {
        return st.tree[node]
    }
 
    st.pushDown(node, left, right)
    mid := left + (right-left)/2
    sum := 0
 
    if queryLeft <= mid {
        sum += st.query(node*2, left, mid, queryLeft, queryRight)
    }
    if queryRight > mid {
        sum += st.query(node*2+1, mid+1, right, queryLeft, queryRight)
    }
    return sum
}

为什么懒标记不会漏

核心不变量是：

• tree[node] 永远表示当前区间的真实答案
• lazy[node] 表示“这段更新已经记到账上了，但还没分发给孩子”

所以查询或继续往下递归前，只要先 pushDown，信息就不会丢。

常见题型

区间和检索

最基础版本就是：

• 单点改值
• 区间求和

对应 LeetCode 307。

动态开点线段树

如果区间范围非常大，比如 0..1e9，但真正访问点很少，就不能直接开 4n 数组。
这时要用“动态开点”：

• 只有访问到某个节点时才创建它
• 常见于日程安排、扫描线、区间覆盖统计

区间最值 / 最大子段和

很多题目只是在换“节点保存的信息”：

• 维护最大值
• 维护最小值
• 维护区间最大子段和

模板框架其实不变，变的是合并函数。

复杂度

操作	时间复杂度
建树	O(n)
单点修改	O(log n)
区间查询	O(log n)
区间修改（懒标记）	O(log n)
空间	O(n)，工程上常写成 4n

什么时候该想到线段树

• 题目是动态区间问题
• 查询不只是求和，还可能是最值、最大连续和之类
• 更新不是单点，而是整段修改
• 需要自定义区间信息合并

如果题目只是“单点改 + 前缀和 / 区间和”，优先级通常还是 树状数组 更高。

易错点

线段树最容易写错的地方

• 每个节点到底维护什么，必须先定义清楚。
• mid 划分后，左右区间必须分别是 [l, mid] 和 [mid+1, r]。
• 懒标记不是“可有可无的优化”，它是区间修改正确性的组成部分。
• pushDown 时别把左右孩子覆盖长度写错。

经典题目

• 区域和检索 - 数组可修改 - LeetCode 307
• 我的日程安排表 III - LeetCode 732
• 统计区间中的整数数目 - LeetCode 2276
• 天际线问题 - LeetCode 218

相关主题

• 树状数组：更轻量，但能力更单一。
• 二叉树：线段树的结构基础。
• 前缀和与差分：静态区间和时更省事。

---

返回：数据结构 | 算法学习导航