c++树形数据结构——线段树，深入讲解c++算法最重要的数据结构之一！

线段树是一种高效维护区间信息的数据结构，采用二叉树结构将区间操作的时间复杂度优化至O(logN)，适用于区间最值、区间和等查询。核心操作包括建树、区间修改和查询，其中懒标记(Lazy Tag)技术通过延迟处理实现高效区间更新。建树从根节点递归构建，修改和查询时需先下放懒标记再处理子节点。注意除法等非线性操作不适合使用懒标记。例题展示了如何用线段树实现区间修改和求和，体现了其处理大规模数据的高效性。

qizhiburce

801人浏览 · 2025-11-16 16:17:46

qizhiburce · 2025-11-16 16:17:46 发布

注：本文例题均来自蓝桥杯官网公开真题，仅用于技术学习与算法讲解

一，线段树简介

        线段树是非常重要的数据结构之一，线段树似一棵二叉树，维护一个数组a[n]的区间信息，它可以将区间修改，查询的时间复杂度降低到o(logN)，线段树可以维护区间最值，区间和，区间异或和，区间gcd等信息。
         例如：要用一棵线段树来维护数组区间的元素和，在线段树中，每个节点有一个权值，表示一段区间（也叫做一条线段）的和，我们规定节点l为根节点其管辖区间为[1,n]。
         对于一个节点x，其管辖区间为[l,r],mid=(l+r)/2,该节点权值为左右儿子权值之和，左儿子编号为2x，管辖区间为[1,mid],右儿子编号为2x+1，管辖区间为[mid+1,r]，对于线段树的所有操作必须从根开始往下走，管辖区间无需存储下来，从[1,n]开始计算即可。

如图：（来自蓝桥杯官网）

二，线段树相关操作

（一），建树

建树通过递归实现，从节点1开始，逐个往下遍历，直到叶子节点（即管辖区间为1的节点），填入数组元素，在子节点处理完毕后更新当前节点信息。
注意：每个节点所含的要素：节点编号，管辖区间，lz增量！！！

1，pushup

void pushup(int k)
{
    t[k] = t[k << 1] + t[k << 1 | 1];
    //t:每个节点保存一个区间 [s, e] 的信息（如区间和、最大值等）
}

2，build

//[s,e]表示管辖区间，o表示当前节点编号
void build(int s = 1, int e = n, int o = 1)
{
    if (s == e)
    {
        //递归出口
        t[o] = a[s];
        return;
        /*当区间长度为 1 时（s == e），到达叶子节点。
叶子节点直接存储原始数组 a 中的值 a[s]。*/
    }
    int mid = (s + e) >> 1;
    /*mid = (s + e) >> 1：计算区间中点（等价于 (s+e)/2）。
左子树管辖区间 [s, mid]，节点编号为 o << 1（即 o*2）。
右子树管辖区间 [mid+1, e]，节点编号为 o << 1 | 1（即 o*2+1）。*/
    build(s, mid, o << 1);
    build(mid + 1, e, o << 1 | 1);
    //将[s,e]分为两个区间[s,mid] [mid+1,e]
    //将子节点合并到当前节点
    /*递归返回时，调用 pushup 将左右子树的信息合并到当前节点。
确保父节点的值在子节点更新后正确反映区间信息。*/
    pushup(o);//整合
}

（二），区间修改和区间查询（核心部分）

先说一下lazytag：lz 是线段树中用于实现懒标记（Lazy Propagation）的数组，其核心作用是延迟处理区间更新操作，避免每次更新都递归到叶子节点，从而将时间复杂度优化到 O(logn)。
假设我们要对区间 [1, 1000] 进行 1000 次更新操作。如果没有懒标记，每次更新都需要递归到叶子节点，时间复杂度为 O(1000×log1000)，效率较低。

         区间修改和区间查询的框架几乎一样，流程都是：
         1，检查递归出口，若当前区间[s,e]是查询、修改区间[l,r]的子区间，说明找到了需要修改的点。
         2，将lazytag下放，lazytag[i]表示的是节点i还需要给儿子节点修改的信息，但是暂时还没执行（为了更低的时间复杂度，这是必须要的）。
         3，向两个儿子走（判断是否应该走，即儿子的区间是否和[l,r]有交集）若无这一步则要走遍整个叶子节点。

1，pushdown：传递懒标记

void pushdown(int s, int e, int o)//功能：将当前节点 o 的懒标记 lz[o] 下推到左右子节点，
//并更新子节点的区间和 t。逻辑：传递与销毁
{
    if (lz[o])// 检查当前节点o是否有未下推的懒标记
    {// 计算左右子节点应增加的值
        //lz 数组存储的是待下推的增量值。
        int ls = o << 1, rs = o << 1 | 1, mid = (s + e) >> 1;
        //将lz[o]信息增加给左儿子的t和lz
        // 将懒标记传递给子节点
        //只有是完全的子区间才有lz（见手机图），若只有交集，则还要继续往下递归
        t[ls] += (mid - s + 1) * lz[o], lz[ls] += lz[o];
        t[rs] += (e - mid) * lz[o], lz[rs] += lz[o];
        // 清空当前节点的懒标记
        lz[o] = 0;
    }

    /*示例[1, 2 ,3 ,4]
假设当前节点 o 表示区间 [1, 4]，lz[o] = 2（表示该区间所有元素需加 2），且 t[o] = 10（原区间和为 10）。
下推时：
左子节点 [1, 2]：
t[ls] += (2-1+1)*2 = 4（左子区间和增加 4）。
lz[ls] += 2（左子节点记录待处理的增量 2）。
右子节点 [3, 4]：
t[rs] += (4-3+1)*2 = 4（右子区间和增加 4）。
lz[rs] += 2（右子节点记录待处理的增量 2）。
当前节点：lz[o] = 0（标记已处理）。*/
}

2，update ：更新区间

void update(int l, int r, ll v, int s = 1, int e = n, int o = 1)
//后面3个量是初始化的，所以在主函数中不需要写
//从根节点开始遍历
/*功能：将区间 [l, r] 内每个元素加上 v。
* 我要更新那一段区间和，就是要更新与它所有相关（有交集）的区间！！！
参数：
l, r：待更新的目标区间。
v：要增加的值。
s, e：当前递归到的区间（默认根节点为 [1, n]）。 
o：当前节点编号（默认根节点为 1）。*/
{
    if (l <= s && e <= r)
    {
        //当前节点是要修改区间的某个子区间，可以停止了
        t[o] += (e - s + 1) * v;//表示将区间内每个节点都加上v
        lz[o] += v;//表示当前节点的子节点还有v需要修改
        //表示只有完全的子区间才有lz，否则没有
        return;
    }
    int mid = (s + e) >> 1;
    pushdown(s, e, o);//将lz下放
    //此时必有s<=r,再加上mid>=1即可保证[s,mid]和[l,r]有交集
    //因为若s>r,则[l,r]...[s,e]二者完全没有交集，就无法进入该函数了
    if (mid >= l)update(l, r, v, s, mid, o << 1);// 递归左子树
    if (mid + 1 <= r)update(l, r, v, mid + 1, e, o << 1 | 1);// 递归右子树
    //有交集，就再递归
    pushup(o);//整合
}
//只有是完全的子区间才有lz（见手机图）
/*lz 数组的值在以下情况发生变化：
更新时：若当前节点完全包含在目标区间内，lz 增加修改量。
下推时：将 lz 拆分到子节点，并清空自身。
累积时：对同一区间多次更新，lz 值叠加。*/
/*若对同一区间多次更新，lz 值会累积。例如：
第一次 update(1, 4, 2)：根节点 lz[1] = 2。
第二次 update(1, 4, 3)：根节点 lz[1] = 2 + 3 = 5。*/
/*示例说明
假设线段树维护数组 [1, 2, 3, 4]，初始时：
t[1] = 10（根节点表示整个区间和）。
lz 数组全为 0。
若调用 update(1, 4, 2)（将整个区间加 2）：
根节点区间 [1, 4] 完全包含在 [1, 4] 内，直接更新：
t[1] = 10 + (4-1+1)*2 = 18。
lz[1] = 2（记录子节点需要加 2）。
此时若查询区间 [1, 2]：
递归到根节点的左子节点 [1, 2] 前，调用 pushdown：
t[左子节点] = 3 + (2-1+1)*2 = 7。
lz[左子节点] = 2。
lz[1] = 0（根节点懒标记清空）。*/

3，query：求区间和

ll query(int l, int r, int s = l, int e = n, int o = 1)
{
    if (l <= s && e <= r)//这一句相当于节点o的管辖区间正好处于要求的区间[l,r]内！可以直接返回t[o]，这是递归终点的情况！
    {
        //当前节点是要修改的区间的某个子区间，可以停止了
        return t[o];
    }
    /*回到你说的 [3,4] 节点（假设存在这样一个节点）：
如果 [3,4] 完全被 [2,5] 包含，它返回的 t[o] 只是 [3,4] 的和。
但 [2,2] 和 [5,5] 的部分会由其他节点（比如 [1,2] 的右半、[4,5] 的右半）负责计算，
最终所有相关节点的结果会累加起来，得到 [2,5] 的完整总和*/
    int mid = (s + e) >> 1;
    pushdown_the_lz(s, e, o);
    ll res = 0;
    if (mid >= l)res += query(l, r, s, mid, o << 1);
    if (mid + 1 <= r)res += query(l, r, mid + 1, e, o << 1 | 1);
    //有交集，就再递归
    return res;
}

三，一些注意事项

        有些特殊的修改无需使用lazytag, 例如除法，开根号，求欧拉函数等，因为其时间复杂度相近。
        在线段树中，懒标记（Lazy Tag）的核心作用是通过 “合并多次同类操作” 减少递归次数，
从而将区间更新的时间复杂度从 O(n)优化到 O(logn)。但对于除法、开根号、求欧拉函数等特殊操作，往往不需要懒标记，核心原因是这些操作不满足 “可合并性”，且即使直接递归到叶子节点，
实际时间复杂度也与 “带懒标记的优化方案” 相近，甚至更简单。
        非线性幂运算（如平方、立方等）动态模运算（模的参数不固定）区间排序（如升序、降序排列）等亦不适合。

1. 懒标记的适用前提：操作具有 “可合并性”
        懒标记能生效的关键是操作本身可以被 “累积” 或 “合并”。例如：
        加法：对区间先加
a再加b，等价于直接加a+b（合并为一次操作）。
        乘法：对区间先乘a再乘b，等价于直接乘a×b（合并为一次操作）。
这些操作的 “合并性” 使得我们可以用一个标记（如 lz[o]）记录累积的修改量，
延迟到需要访问子节点时再下推，从而减少递归次数。
2. 特殊操作无需懒标记的核心原因：

（1）操作不具备 “累积性”，无法用标记合并。
（2）操作具有 “收敛性”，直接递归的实际复杂度不高（3）操作依赖 “元素个体”，无法对区间整体标记。

四，例题训练

例题1：蓝桥杯官网——区间修改、区间求和

题目描述

给定一个长度为 N 的数组 aa，其初值分别为 a1,a2,...,aN。

现有 Q 个操作，操作有以下两种：

1 l r k，将区间 al,al+1,...ar 的值加上 k。
2 l r，求区间 al+1,...,ar 的和为多少。

输入描述

输入第 1 行包含两个正整数 N,Q，分别表示数组 a 的长度和操作的个数。

第 2 行包含 N 个非负整数 a1,a2,...,aN，表示数组 a 元素的初值。

第 3∼Q−2 行每行表示一共操作，格式为以下两种之一：

1 l r x
2 l r

其含义如题所述。

1≤N,Q≤10^5，1≤l≤r≤N，−10^9≤k,ai≤10^9。

输出描述

输出共 Q 行，每行包含一个整数，表示相应查询的答案。

输入输出样例

示例 1

输入：

输出：

3
8
22

代码详解：

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], t[N * 4], lz[N * 4], n;//注意t，lz的处理范围较大,n开全局，方便处理
//问题：线段树的节点数量通常是 4*N（为了覆盖所有可能的子节点），
// 而 lz 数组（懒标记）需要与节点数量对应。

void pushup(int o)
{
    t[o] = t[o << 1] + t[o << 1 | 1];
}

void build(int s = 1, int e = n, int o = 1)
{
    //出口
    if (s == e)
    {
        t[o] = a[s];//叶子节点的管辖区间的长度必定为一！！！！！！！！！[1,1] [4,4]
        return;
    }
    int mid = (s + e) >> 1;
    build(s, mid, o << 1), build(mid + 1, e, o << 1 | 1);//递归左右子树
    pushup(o);//整合
}

void pushdown(int s, int e, int o)
{
    if (lz[o])
    {
        int ls = o << 1, rs = o << 1 | 1, mid = (s + e) >> 1;
        t[ls] += 1ll * (mid - s + 1) * lz[o], lz[ls] += lz[o];
        t[rs] += 1ll * (e - mid) * lz[o], lz[rs] += lz[o];
        /*赋值操作（=）：会直接覆盖子节点的原有值，导致历史更新丢失。
    正确逻辑：应使用累加操作（+=），将懒标记的影响累加到子节点的当前值上。*/
        lz[o] = 0;//不要忘了清空
    }
}
/*
在这段代码中，1ll 是为了防止整数溢出，确保乘法运算的结果能正确表示。具体原因如下：
1. 数据类型的隐式转换规则
1ll 表示 长整型（long long）的 1。当它与其他整数类型（如 int）进行运算时，编译器会触发 隐式类型转换：将 int 类型的变量自动转换为 long long 类型后再参与运算，最终结果也是 long long 类型。
2. 为什么需要转换？
代码中涉及的变量：
(mid - s + 1) 和 (e - mid) 是区间长度，类型为 int（假设 s, e, mid 都是 int）。
lz[o] 是懒标记，类型通常也是 int。
如果直接计算 (mid - s + 1) * lz[o]，两个 int 相乘的结果仍为 int。若区间长度较大（例如接近 1e9）且 lz[o] 也较大时，乘积可能超过 int 的最大值（约 2e9），
导致 整数溢出（结果变为负数或错误值）。
*/


void update(ll l, ll r, ll v, int s = 1, int e = n, int o = 1)
{//这里一定注意，前3个变量是ll，不是int（由主函数）,否则会有部分测试用例过不了
  //当完全属于子集是才有lz
    if (l <= s && e <= r)
    {
        t[o] += (e - s + 1) * v;
        lz[o] += v;
        return;
    }
    //否则就要左右递归(在只有交集的情况),但先要下放lz
    pushdown(s, e, o);
    int mid = (s + e) >> 1;
    if (mid >= l)update(l, r, v, s, mid, o << 1);
    if (mid + 1 <= r)update(l, r, v, mid + 1, e, o << 1 | 1);
    pushup(o);
}

ll query(ll l, ll r, int s = 1, int e = n, int o = 1)
{
    //当完全属于子集是才有lz
    if (l <= s && e <= r)
    {
        return t[o];
    }
    //否则就要左右递归(在只有交集的情况),但先要下放lz
    pushdown(s, e, o);
    int mid = (s + e) >> 1;
    ll res = 0;
    if (mid >= l)res += query(l, r, s, mid, o << 1);
    if (mid + 1 <= r)res += query(l, r, mid + 1, e, o << 1 | 1);
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int q; cin >> n >> q;
    for (int i = 1; i <= n; i++)cin >> a[i];
    //建树
    build();
    while (q--)
    {
        int op; cin >> op;
        if (op == 1)
        {
            ll l, r, x; cin >> l >> r >> x;
            update(l, r, x);
        }
        else
        {
            ll l, r; cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
    return 0;
}

例题2：蓝桥杯官网——区间开根号

问题描述

给定一个数组 x，有以下操作：

1 l r，将数组 x 的 [l,r] 区间内所有数替换为 xi，仅保留整数。
2 l r，求 [l,r] 区间内所有数的和。

输入格式

输入的第一行为两个正整数 n,m，分别表示数组大小和操作次数。

接下来为一个长度为 n 的数组 x，仅包含整数。

接下来 m 行，每行三个整数，含义见问题描述。

输出格式

对于操作 2，每个操作输出一行，每行仅包括一个整数，含义见问题描述。

样例输入

样例输出

3
6
13

评测数据规模

对于 50% 的评测数据，1≤n,m≤50,1≤xi≤5000。

对于 100% 的评测数据，1≤n,m≤2⋅10^5,1≤l,r≤n,1≤xi≤10^9。

代码详解：

#include <iostream>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
//区间开根号，无需懒标记
ll a[N], t[N * 4], n;//注意t，lz的处理范围较大,n开全局，方便处理
//t在这里仍是区间和

void pushup(int o)
{
    t[o] = t[o << 1] + t[o << 1 | 1];
}

void build(int s = 1, int e = n, int o = 1)
{
    //出口
    if (s == e)
    {
        t[o] = a[s];
        return;
    }
    int mid = (s + e) >> 1;
    build(s, mid, o << 1), build(mid + 1, e, o << 1 | 1);//递归左右子树
    pushup(o);//整合
}

void update(ll l, ll r, int s = 1, int e = n, int o = 1)
{
    //剪枝
    if (t[o] == e - s + 1)return;//说明该该区间的数字全为1，无需再开根号
    if (s == e)
    {
        t[o] = sqrt(t[o]);
        return;
    }
    //否则就要左右递归(在只有交集的情况)
    int mid = (s + e) >> 1;
    if (mid >= l)update(l, r, s, mid, o << 1);
    if (mid + 1 <= r)update(l, r, mid + 1, e, o << 1 | 1);
    pushup(o);
}

ll query(ll l, ll r, int s = 1, int e = n, int o = 1)
{
    //当完全属于子集是才有lz
    if (l <= s && e <= r)
    {
        return t[o];
    }
    //否则就要左右递归(在只有交集的情况)
    int mid = (s + e) >> 1;
    ll res = 0;
    if (mid >= l)res += query(l, r, s, mid, o << 1);
    if (mid + 1 <= r)res += query(l, r, mid + 1, e, o << 1 | 1);
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int q; cin >> n >> q;
    for (int i = 1; i <= n; i++)cin >> a[i];
    //建树
    build();
    while (q--)
    {
        int op; cin >> op;
        if (op == 1)
        {
            ll l, r, x; cin >> l >> r;
            update(l, r);
        }
        else
        {
            ll l, r; cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
    return 0;
}

例题3：蓝桥杯官网——第一个数

问题描述

给定一个大小为 n 的序列 a ，以及 q 次操作，每次操作为下列操作之一：

1 x y 表示将序列中第 x 个数修改为 y 。

2 p 表示查询序列中第一个不小于 p 的数的位置。

输入格式

第一行给定一个正整数 n 。

第二行输入 n 个数表示序列 a 。

第三行输入一个正整数 q 表示有 q 次询问

接下来 q 行，对于操作 1 给定三个正整数分别表示操作类型 op ，修改位置 x 以及修改值 y。对于操作 2 给定两个正整数分别表示操作类型 op 以及需要查询的数 p 。

输出格式

对于每个操作 2 ，每次输出一个正整数，表示第一个不小于 x 的数的位置，如果不存在则输出 −1 。

输入案例

6
5 4 4 3 9 1
5
2 3
2 10
1 5 10
2 10
2 6

样例输出

说明

对于第一次操作，序列中第一个大于 3 的数为 5，他的位置为 1 ,所以输出 1。对于第三次操作，由于序列中没有比 10 大的数，故输出 −1。

评测数据规模

对于 100% 的评测数据。
1≤n≤2×10^5，1≤ai≤10^9 ，1≤q≤2×10^5 ，1≤op≤2 ，1≤x≤n，1≤y,p≤10^9。

代码详解：

#include <iostream>
using namespace std;
using ll=long long;
const int N=2e5+9;
ll a[N],t[N*4],lz[N*4],n;//注意t，lz的处理范围较大,n开全局，方便处理
//这里t可以表示管辖区间的最大值

void pushup(int o)
{
  t[o]=max(t[o<<1],t[o<<1|1]);
}

void build(int s=1,int e=n,int o=1)
{
  //出口
  if(s==e)
  {
    t[o]=a[s];
    return;
  }
  int mid=(s+e)>>1;
  build(s,mid,o<<1),build(mid+1,e,o<<1|1);//递归左右子树
  pushup(o);//整合
}

void pushdown(int s,int e,int o)
{
  //这里将值修改该为了将区间修改即单区间[k,k]
  if(lz[o])
  {
    int ls=o<<1,rs=o<<1|1,mid=(s+e)>>1;
    t[ls]=lz[o],lz[ls]=lz[o];//这里t表示管辖区间最大值，由update函数，
    //将待修改区的元素全部都修改为v，则最大值也为v
    //有由于为子集才有lz，所以在该子集中最大值也为v，即lz[o]
    t[rs]=lz[o],lz[rs]=lz[o];//这里在多次查询时，只是修改数据，t,lz无需累加
    lz[o]=0;//不要忘了清空
  }
}


void update(ll l,ll r,ll v,int s=1,int e=n,int o=1)//相当于要将区间[l,r]的值都修改为v
{//这里一定注意，前3个变量是ll，不是int（由主函数）,否则会有部分测试用例过不了
  //当完全属于子集是才有lz
  if(l<=s&&e<=r)
  {
    t[o]=v;
    lz[o]=v;
    return;
  }
  //否则就要左右递归(在只有交集的情况),但先要下放lz
  pushdown(s,e,o);
  int mid=(s+e)>>1;
  if(mid>=l)update(l,r,v,s,mid,o<<1);
  if(mid+1<=r)update(l,r,v,mid+1,e,o<<1|1);
  pushup(o);
}

ll query(ll l,ll r,int s=1,int e=n,int o=1)//这里query是查询[l,r]的最大值
{
  //当完全属于子集是才有lz
  if(l<=s&&e<=r)
  {
    return t[o];
  }
  //否则就要左右递归(在只有交集的情况),但先要下放lz
  pushdown(s,e,o);
  int mid=(s+e)>>1;
  ll res=0;//对于有交集的区间，巨不断递归取交集部分，更新最大值
  if(mid>=l)res=max(res,query(l,r,s,mid,o<<1));
  if(mid+1<=r)res=max(res,query(l,r,mid+1,e,o<<1|1));
  return res;
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int q;cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  //建树
  build();
  cin>>q;
  while(q--)
  {
    int op;cin>>op;
    if(op==1)
    {
      ll k,x;cin>>k>>x;
      update(k,k,x);
    }
    else
    {
      ll p;cin>>p;//高能二分
      ll l=0,r=n+1;
      while(l+1!=r)
      {
        int mid=(l+r)>>1;
        if(query(1,mid)>=p)r=mid;
        else l=mid;
      }
      cout<<(r==n+1?-1:r)<<'\n';//题目中要输出的是位置，而不是数本身！
      //由题意，不存在就输出-1
    }
  }
  return 0;
}

创作不易，大家不妨点赞关注支持一下？