线段树模板

一句话说明

线段树模板最核心的不是背代码，而是固定三件事：节点维护什么、怎么合并、什么时候下传懒标记。

先记模板适用场景

当题目出现下面这些信号时，优先考虑线段树：

• 区间查询
• 单点修改
• 区间修改
• 需要动态维护最值 / 区间和

如果只是“单点改 + 前缀和”，通常 树状数组模板 更轻。

Go 模板：区间加 + 区间和

type SegmentTree struct {
    n    int
    tree []int
    lazy []int
}
 
func NewSegmentTree(nums []int) *SegmentTree {
    st := &SegmentTree{
        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 *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) apply(node, left, right, delta int) {
    st.tree[node] += (right - left + 1) * delta
    st.lazy[node] += delta
}
 
func (st *SegmentTree) pushDown(node, left, right int) {
    if st.lazy[node] == 0 || left == right {
        return
    }
 
    mid := left + (right-left)/2
    delta := st.lazy[node]
    st.apply(node*2, left, mid, delta)
    st.apply(node*2+1, mid+1, right, delta)
    st.lazy[node] = 0
}
 
func (st *SegmentTree) RangeAdd(queryLeft, queryRight, delta int) {
    if st.n == 0 || queryLeft > queryRight {
        return
    }
    st.rangeAdd(1, 0, st.n-1, queryLeft, queryRight, delta)
}
 
func (st *SegmentTree) rangeAdd(node, left, right, queryLeft, queryRight, delta int) {
    if queryLeft <= left && right <= queryRight {
        st.apply(node, left, right, delta)
        return
    }
 
    st.pushDown(node, left, right)
    mid := left + (right-left)/2
 
    if queryLeft <= mid {
        st.rangeAdd(node*2, left, mid, queryLeft, queryRight, delta)
    }
    if queryRight > mid {
        st.rangeAdd(node*2+1, mid+1, right, queryLeft, queryRight, delta)
    }
 
    st.tree[node] = st.tree[node*2] + st.tree[node*2+1]
}
 
func (st *SegmentTree) RangeSum(queryLeft, queryRight int) int {
    if st.n == 0 || queryLeft > queryRight {
        return 0
    }
    return st.rangeSum(1, 0, st.n-1, queryLeft, queryRight)
}
 
func (st *SegmentTree) rangeSum(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.rangeSum(node*2, left, mid, queryLeft, queryRight)
    }
    if queryRight > mid {
        sum += st.rangeSum(node*2+1, mid+1, right, queryLeft, queryRight)
    }
 
    return sum
}

这个模板的三个不变量

• tree[node] 永远表示当前区间的真实答案
• lazy[node] 表示这段更新还没下传给孩子
• 部分覆盖继续递归前，必须先 pushDown

最常改哪几处

改维护信息

如果不是区间和，而是区间最大值 / 最小值，就改：

• tree[node] 的含义
• 合并逻辑

改更新类型

如果是区间赋值而不是区间加法，就要改：

• lazy 的含义
• apply 的处理方式
• 可能需要额外标记区分“是否有赋值懒标记”

易错点

线段树模板最容易错的地方

• 区间长度一定是 right-left+1。
• 左右子区间固定是 [left, mid] 和 [mid+1, right]。
• 完全覆盖时直接处理当前节点，不要继续递归到底。
• 懒标记如果不下传，查询和后续修改会错。

复杂度

操作	时间复杂度	空间复杂度
建树	O(n)	O(n)
区间修改	O(log n)	O(1) 额外递归栈除外
区间查询	O(log n)	O(1) 额外递归栈除外

相关主题

• 线段树
• 树状数组模板

---

返回：算法模板