博客详情 - oirush

admin 的博客
线段树 (Segment Tree)
admin SU @ 2026-6-7 19:59:48

一、算法概述

线段树（Segment Tree） 是一种基于二叉树的高效区间操作数据结构。它支持区间修改和区间查询操作，每个节点代表一个区间，左右子节点分别代表该区间的左半和右半部分。

相比于树状数组，线段树功能更强大（支持区间修改 + 区间查询，且不要求运算可逆），但实现更复杂、常数略大。

二、核心思想

2.1 树的结构

线段树是一棵平衡二叉树：

叶子节点：对应原数组的单个元素
内部节点：对应一段连续区间，其值由左右子节点合并得到（如区间和 = 左儿子区间和 + 右儿子区间和）
根节点：对应整个数组 [1, n]

对于大小为 n 的数组，通常需要开辟 4n 的空间来存储线段树。

2.2 懒标记 (Lazy Tag)

当需要区间修改时，如果逐一下沉到每个叶子节点，复杂度将退化为 O(n)。

懒标记的核心思想：当修改区间完全覆盖当前节点区间时，直接更新当前节点值并打上标记，不再向下递归。当后续查询或修改需要访问该节点的子节点时，再将标记**下推（pushdown）**到子节点。

这样保证了每次操作最多涉及 O(log n) 个节点。

2.3 关键操作

build：递归建树，叶子节点赋初值，内部节点合并子节点值
pushdown：将当前节点的懒标记下传给左右子节点
update：区间更新，若当前区间完全在目标区间内则打标记，否则 pushdown 后递归处理
query：区间查询，若当前区间完全在目标区间内则直接返回，否则 pushdown 后递归合并

三、算法步骤 / 伪代码

建树 (Build)

function build(node, l, r):
    if l == r:
        tree[node] = arr[l]
        return
    mid = (l + r) / 2
    build(node * 2, l, mid)
    build(node * 2 + 1, mid + 1, r)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]

懒标记下推 (Pushdown)

function pushdown(node, l, r):
    if lazy[node] != 0:
        mid = (l + r) / 2
        // 更新左儿子
        tree[node * 2] += lazy[node] * (mid - l + 1)
        lazy[node * 2] += lazy[node]
        // 更新右儿子
        tree[node * 2 + 1] += lazy[node] * (r - mid)
        lazy[node * 2 + 1] += lazy[node]
        // 清除当前标记
        lazy[node] = 0

区间更新 (Update)

function update(node, l, r, ql, qr, delta):
    if ql <= l and r <= qr:
        tree[node] += delta * (r - l + 1)
        lazy[node] += delta
        return
    pushdown(node, l, r)
    mid = (l + r) / 2
    if ql <= mid: update(node * 2, l, mid, ql, qr, delta)
    if qr > mid:  update(node * 2 + 1, mid + 1, r, ql, qr, delta)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]

区间查询 (Query)

function query(node, l, r, ql, qr):
    if ql <= l and r <= qr:
        return tree[node]
    pushdown(node, l, r)
    mid = (l + r) / 2
    result = 0
    if ql <= mid: result += query(node * 2, l, mid, ql, qr)
    if qr > mid:  result += query(node * 2 + 1, mid + 1, r, ql, qr)
    return result

四、C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    vector<long long> tree;   // 线段树节点值
    vector<long long> lazy;   // 懒标记（加法）
    int n;

    // ========== 建树 ==========
    void build(int node, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[node] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(node * 2, l, mid, arr);
        build(node * 2 + 1, mid + 1, r, arr);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // ========== 懒标记下推 ==========
    void pushdown(int node, int l, int r) {
        if (lazy[node] != 0) {
            int mid = l + (r - l) / 2;
            // 下推给左儿子
            tree[node * 2] += lazy[node] * (mid - l + 1);
            lazy[node * 2] += lazy[node];
            // 下推给右儿子
            tree[node * 2 + 1] += lazy[node] * (r - mid);
            lazy[node * 2 + 1] += lazy[node];
            // 清除当前懒标记
            lazy[node] = 0;
        }
    }

    // ========== 区间加法更新 ==========
    void update(int node, int l, int r, int ql, int qr, long long delta) {
        // 当前区间完全在目标区间内
        if (ql <= l && r <= qr) {
            tree[node] += delta * (r - l + 1);
            lazy[node] += delta;
            return;
        }
        pushdown(node, l, r);
        int mid = l + (r - l) / 2;
        if (ql <= mid) update(node * 2, l, mid, ql, qr, delta);
        if (qr > mid)  update(node * 2 + 1, mid + 1, r, ql, qr, delta);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // ========== 区间和查询 ==========
    long long query(int node, int l, int r, int ql, int qr) {
        // 当前区间完全在目标区间内
        if (ql <= l && r <= qr) {
            return tree[node];
        }
        pushdown(node, l, r);
        int mid = l + (r - l) / 2;
        long long result = 0;
        if (ql <= mid) result += query(node * 2, l, mid, ql, qr);
        if (qr > mid)  result += query(node * 2 + 1, mid + 1, r, ql, qr);
        return result;
    }

public:
    // ========== 构造函数 ==========
    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n + 5, 0);
        lazy.resize(4 * n + 5, 0);
        build(1, 0, n - 1, arr);  // 0-indexed 建树
    }

    // ========== 对外接口：区间 [l, r] 增加 delta ==========
    void rangeAdd(int l, int r, long long delta) {
        update(1, 0, n - 1, l, r, delta);
    }

    // ========== 对外接口：区间 [l, r] 求和 ==========
    long long rangeSum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    // ========== 单点修改 ==========
    void pointUpdate(int index, long long val) {
        long long old = rangeSum(index, index);
        rangeAdd(index, index, val - old);
    }
};

// ==================== 测试主函数 ====================
int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};

    cout << "===== 初始化线段树 =====" << endl;
    SegmentTree seg(arr);

    cout << "原数组: ";
    for (int v : arr) cout << v << " ";
    cout << endl;

    // 区间查询测试
    cout << "\n===== 区间查询 =====" << endl;
    cout << "sum[0, 2] = " << seg.rangeSum(0, 2) << " (期望: 9)" << endl;   // 1+3+5
    cout << "sum[1, 4] = " << seg.rangeSum(1, 4) << " (期望: 24)" << endl;  // 3+5+7+9
    cout << "sum[0, 5] = " << seg.rangeSum(0, 5) << " (期望: 36)" << endl;  // 全部

    // 区间修改测试
    cout << "\n===== 区间加法 =====" << endl;
    seg.rangeAdd(1, 3, 10);  // arr[1..3] 各加 10 => 3->13, 5->15, 7->17
    cout << "执行 rangeAdd(1, 3, 10) 后:" << endl;
    cout << "sum[0, 2] = " << seg.rangeSum(0, 2) << " (期望: 1+13+15=29)" << endl;
    cout << "sum[1, 4] = " << seg.rangeSum(1, 4) << " (期望: 13+15+17+9=54)" << endl;
    cout << "sum[0, 5] = " << seg.rangeSum(0, 5) << " (期望: 1+13+15+17+9+11=66)" << endl;

    // 单点查询
    cout << "单点 arr[2] = " << seg.rangeSum(2, 2) << " (期望: 15)" << endl;

    // 再次区间修改（测试懒标记叠加）
    cout << "\n===== 懒标记叠加测试 =====" << endl;
    seg.rangeAdd(0, 5, 2);  // 全数组 +2
    cout << "执行 rangeAdd(0, 5, 2) 后:" << endl;
    cout << "sum[0, 5] = " << seg.rangeSum(0, 5) << " (期望: 66 + 2*6 = 78)" << endl;
    cout << "sum[2, 4] = " << seg.rangeSum(2, 4) << " (期望: 15+17+9 + 2*3 = 47)" << endl;

    // 单点修改测试
    cout << "\n===== 单点修改 =====" << endl;
    seg.pointUpdate(3, 100);  // arr[3] 设为 100
    cout << "执行 pointUpdate(3, 100) 后:" << endl;
    cout << "arr[3] = " << seg.rangeSum(3, 3) << " (期望: 100)" << endl;
    cout << "sum[0, 5] = " << seg.rangeSum(0, 5) << " (期望: 78 - 19 + 100 = 159)" << endl;

    return 0;
}

五、复杂度分析

操作	时间复杂度	说明
建树 (Build)	O(n)	每个节点访问一次，共约 2n 个节点
区间更新 (Update)	O(log n)	每层最多访问 4 个节点（懒标记剪枝）
区间查询 (Query)		每层最多访问 4 个节点
单点操作		区间操作的退化情况

树高 O(log n)：完全二叉树高度不超过 ⌈log₂n⌉ + 1
节点数量：约 2n（实际开辟 4n 空间以简化下标计算）
懒标记：保证区间修改不会退化为 O(n)

与树状数组对比

特性	线段树	树状数组
区间修改 + 区间查询	✅ 支持	⚠️ 需要两个 BIT
非可逆运算（如 max/min）	✅ 支持	❌ 不支持
实现复杂度	较复杂	简单
空间	4n	n
常数	较大	极小

六、应用场景

场景	说明
区间求和 / 最值查询	动态维护数组的区间和、区间最大/最小值
区间染色 / 覆盖问题	墙上海报、区间覆盖长度统计
历史版本查询	配合可持久化线段树（主席树）查询历史区间第 K 小
扫描线算法	矩形面积并、周长并等几何问题
动态 DP	树链剖分配合线段树进行树上路径查询
区间开根号	势能线段树，利用值域有限性剪枝
二维线段树	矩阵子区域查询与修改

七、经典例题

区间和查询与修改

本文第四节的 C++ 代码已完整实现线段树的建树、区间加法更新、区间和查询、单点修改功能，可直接处理以下类型的题目：

给定初始数组，支持两种操作
操作一：将区间 [l, r] 的所有元素加上 val
操作二：查询区间 [l, r] 的元素之和

核心要点回顾：

使用 tree[node] 存储当前节点对应区间的和
使用 lazy[node] 存储当前节点待下推的加法增量
pushdown 将懒标记均分给左右儿子，更新儿子节点的 tree 和 lazy
区间覆盖时直接更新并打标记，无需递归到叶子

进一步练习：

LeetCode 699：掉落的方块（线段树维护区间最大值 + 坐标离散化）
LeetCode 732：我的日程安排表 III（线段树维护区间最大重叠次数 / 差分）
Luogu P3372：【模板】线段树 1（区间加 + 区间求和，经典模板题）
Luogu P3373：【模板】线段树 2（区间加 + 区间乘 + 区间求和，多懒标记）
修改懒标记实现区间赋值操作（将 lazy 从 += 改为 =）

线段树 (Segment Tree)

一、算法概述

二、核心思想

2.1 树的结构

2.2 懒标记 (Lazy Tag)

2.3 关键操作

三、算法步骤 / 伪代码

建树 (Build)

懒标记下推 (Pushdown)

区间更新 (Update)

区间查询 (Query)

四、C++ 代码实现

五、复杂度分析

与树状数组对比

六、应用场景

七、经典例题

区间和查询与修改

状态

开发

支持

关于

线段树 (Segment Tree)

一、算法概述

二、核心思想

2.1 树的结构

2.2 懒标记 (Lazy Tag)

2.3 关键操作

三、算法步骤 / 伪代码

建树 (Build)

懒标记下推 (Pushdown)

区间更新 (Update)

区间查询 (Query)

四、C++ 代码实现

五、复杂度分析

与树状数组对比

六、应用场景

七、经典例题

区间和查询与修改

状态

开发

支持

关于

还没有账户？

登录