线段树

00:00

2 min Advanced 2026/6/14

线段树数据结构：区间查询、单点更新、懒标记（Lazy Propagation）与区间修改的原理与实现。

1. 线段树基础

1.1 问题背景

线段树（Segment Tree）用于高效解决区间查询与区间修改问题：

操作	暴力	前缀和	线段树
区间求和	$O (n)$	$O (1)$	$O (lo g n)$
单点修改	$O (1)$	$O (n)$	$O (lo g n)$
区间修改	$O (n)$	-	$O (lo g n)$

1.2 树形结构

线段树是完全二叉树，每个节点代表一个区间：

数组: [1, 3, 5, 7, 9, 11]

线段树:
                [0,5]=36
               /        \
         [0,2]=9         [3,5]=27
        /      \         /      \
    [0,1]=4  [2,2]=5  [3,4]=16  [5,5]=11
    /    \            /    \
[0,0]=1 [1,1]=3  [3,3]=7 [4,4]=9

1.3 存储方式

使用数组存储，节点 i 的子节点为 2i 和 2i+1：

# 数组大小: 4n（足够安全）
tree = [0] * (4 * n)
lazy = [0] * (4 * n)  # 懒标记

2. 基本操作

2.1 建树

def build(tree, arr, node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build(tree, arr, node * 2, start, mid)
        build(tree, arr, node * 2 + 1, mid + 1, end)
        tree[node] = tree[node * 2] + tree[node * 2 + 1]

2.2 单点更新

def update_point(tree, node, start, end, idx, val):
    if start == end:
        tree[node] = val
    else:
        mid = (start + end) // 2
        if idx <= mid:
            update_point(tree, node * 2, start, mid, idx, val)
        else:
            update_point(tree, node * 2 + 1, mid + 1, end, idx, val)
        tree[node] = tree[node * 2] + tree[node * 2 + 1]

2.3 区间查询

def query_range(tree, node, start, end, l, r):
    if r < start or end < l:
        return 0  # 不相交
    if l <= start and end <= r:
        return tree[node]  # 完全包含
    mid = (start + end) // 2
    left_sum = query_range(tree, node * 2, start, mid, l, r)
    right_sum = query_range(tree, node * 2 + 1, mid + 1, end, l, r)
    return left_sum + right_sum

3. 懒标记（Lazy Propagation）

3.1 为什么需要懒标记

区间修改时，如果逐个更新叶子节点，复杂度为 $O (n)$ 。懒标记将修改操作延迟到需要时才执行：

将区间 [2,4] 的每个值加 5:
  不用懒标记: 更新节点 [2,2], [3,3], [4,4] → O(n)
  懒标记:     只在 [2,4] 节点标记 +5 → O(log n)
              查询时才向下传递标记

3.2 懒标记实现

def push_down(tree, lazy, node, start, end):
    if lazy[node] != 0:
        mid = (start + end) // 2
        # 传递给左子树
        tree[node * 2] += lazy[node] * (mid - start + 1)
        lazy[node * 2] += lazy[node]
        # 传递给右子树
        tree[node * 2 + 1] += lazy[node] * (end - mid)
        lazy[node * 2 + 1] += lazy[node]
        # 清除当前标记
        lazy[node] = 0

def update_range(tree, lazy, node, start, end, l, r, val):
    if r < start or end < l:
        return
    if l <= start and end <= r:
        tree[node] += val * (end - start + 1)
        lazy[node] += val
        return
    push_down(tree, lazy, node, start, end)
    mid = (start + end) // 2
    update_range(tree, lazy, node * 2, start, mid, l, r, val)
    update_range(tree, lazy, node * 2 + 1, mid + 1, end, l, r, val)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]

def query_range_lazy(tree, lazy, node, start, end, l, r):
    if r < start or end < l:
        return 0
    if l <= start and end <= r:
        return tree[node]
    push_down(tree, lazy, node, start, end)
    mid = (start + end) // 2
    return (query_range_lazy(tree, lazy, node * 2, start, mid, l, r) +
            query_range_lazy(tree, lazy, node * 2 + 1, mid + 1, end, l, r))

3.3 懒标记工作示意

初始: [1, 3, 5, 7, 9, 11]

操作: add [2,4] +5

        [0,5]=36
       /        \
  [0,2]=9    [3,5]=27(+5, lazy)
             /        \
        [3,4]=16(+5,lazy)  [5,5]=11
        /      \
    [3,3]=7(+5,lazy) [4,4]=9(+5,lazy)

查询 [3,4]:
  push_down [3,5] → 传递给 [3,4] 和 [5,5]
  push_down [3,4] → 传递给 [3,3] 和 [4,4]
  返回 [3,3] + [4,4] = 12 + 14 = 26

4. 复杂度分析

操作	时间复杂度	空间复杂度
建树	$O (n)$	$O (4 n)$
单点更新	$O (lo g n)$	-
区间查询	$O (lo g n)$	-
区间修改（懒标记）	$O (lo g n)$	$O (4 n)$

5. 变体与应用

5.1 区间最大/最小值

def build_max(tree, arr, node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build_max(tree, arr, node * 2, start, mid)
        build_max(tree, arr, node * 2 + 1, mid + 1, end)
        tree[node] = max(tree[node * 2], tree[node * 2 + 1])

5.2 动态开点线段树

当值域很大但实际使用稀疏时，动态创建节点：

class DynamicSegmentTree:
    def __init__(self, lo, hi):
        self.lo, self.hi = lo, hi
        self.left = self.right = None
        self.val = 0
        self.lazy = 0

    def update(self, l, r, val):
        if r < self.lo or self.hi < l:
            return
        if l <= self.lo and self.hi <= r:
            self.val += val * (self.hi - self.lo + 1)
            self.lazy += val
            return
        self._push_down()
        self.left.update(l, r, val)
        self.right.update(l, r, val)
        self.val = self.left.val + self.right.val

    def _push_down(self):
        mid = (self.lo + self.hi) // 2
        if not self.left:
            self.left = DynamicSegmentTree(self.lo, mid)
        if not self.right:
            self.right = DynamicSegmentTree(mid + 1, self.hi)
        if self.lazy:
            self.left.val += self.lazy * (mid - self.lo + 1)
            self.left.lazy += self.lazy
            self.right.val += self.lazy * (self.hi - mid)
            self.right.lazy += self.lazy
            self.lazy = 0

5.3 经典应用

区间求和：带修改的前缀和
区间最值：RMQ 问题
区间计数：满足条件的元素个数
扫描线：矩形面积并
李超线段树：区间最值线段维护

线段树