目录前言一、为什么需要线段树—— 从实际问题说起二、线段树的核心概念一棵维护区间的二叉树2.1 线段树的结构特点2.2 线段树的存储方式2.3 举个例子直观理解线段树三、线段树的构建从 0 到 1 搭建一棵区间树3.1 构建的核心思路3.2 代码实现构建维护区间和的线段树3.3 关键细节说明四、线段树的区间查询拆分 拼凑快速求区间信息4.1 区间查询的核心规则4.2 举个例子查询[3,8]的和4.3 代码实现区间和查询4.4 测试代码构建 查询五、线段树的单点修改更新叶子向上回溯5.1 单点修改的核心规则5.2 举个例子将位置 6 的数增加 35.3 代码实现单点修改5.4 实战洛谷 P3374 树状数组 1线段树解法题目描述输入输出示例完整 AC 代码总结前言在算法竞赛和数据结构开发中我们经常会遇到区间查询和单点修改的问题比如求一个区间的和、最大值或者修改某个位置的数值后再查询。如果用暴力解法面对10^5级别的数据量和操作次数时间复杂度会达到O(n)直接超时而今天要讲的线段树能把这些操作的时间复杂度都降到O(logn)堪称处理区间问题的 “神器”。这篇文章作为线段树的入门教程会从实际问题出发一步步拆解线段树的引入、构建、区间查询、单点修改的核心原理搭配完整的代码实现新手也能轻松看懂下面就让我们正式开始吧一、为什么需要线段树—— 从实际问题说起在学习一个新的数据结构前我们先搞懂它能解决什么问题这样才不会学的云里雾里。假设我们有这样几个经典的区间问题数据量都是n≤105操作次数q≤105多次查询某个区间[l,r]内所有数的和支持两种操作查询区间[l,r]的和、将某个位置的数修改为指定值多次查询某个区间[l,r]的最大值 / 最小值RMQ 问题支持区间修改 区间查询后续进阶内容本文先铺垫基础。如果用普通数组来处理区间查询需要遍历[l,r]时间复杂度O(n)105次操作就是1010次计算直接超时单点修改修改数组某个位置时间复杂度O(1)看似很快但搭配多次查询还是会整体拉胯。那有没有一种数据结构能兼顾高效的区间查询和高效的单点修改答案就是线段树线段树是一棵基于分治思想的二叉树专门用来维护区间信息。它把一个大区间不断拆分成更小的子区间每个节点都维护一个子区间的信息比如和、最大值通过树的层级结构让查询和修改操作都能沿着树的路径快速完成时间复杂度均为O(logn)完美适配大数据量的区间操作问题。前置知识学习线段树需要掌握二叉树、堆的存储方式以及递归和分治思想建议先打好这些基础再看本文。二、线段树的核心概念一棵维护区间的二叉树在正式构建线段树前我们先搞懂它的核心结构和性质这是后续所有操作的基础。2.1 线段树的结构特点线段树的每个节点都对应一个区间节点中存储这个区间的统计信息比如和、最大值、最小值整体满足以下规则根节点对应整个原始区间比如数组a[1...10]的根节点对应[1,10]存储整个数组的和叶子节点对应原始数组的单个元素也就是长度为 1 的区间比如[1,1]、[2,2]存储数组中对应位置的数值非叶子节点将自己的区间等分为两个子区间分别对应左孩子和右孩子。比如节点[1,10]会拆分为左孩子[1,5]和右孩子[6,10]节点的信息由左右孩子的信息合并而来比如区间和 左孩子和 右孩子和。2.2 线段树的存储方式线段树是一棵完全二叉树近似因此可以用数组来静态存储和堆的存储方式一致这种方式实现简单效率也高若父节点的编号为p则左孩子编号为2∗p简写为p1右孩子编号为2∗p1简写为p1∣1为了避免数组越界线段树的数组大小一般开原始数组大小的 4 倍这是经验值能保证足够存储所有节点。2.3 举个例子直观理解线段树以数组a[5,1,3,0,2,2,7,4,5,8]下标 1~10为例我们构建一个维护区间和的线段树结构如下根节点[1,10]sum37整个数组的和根节点的左孩子[1,5]sum11右孩子[6,10]sum26[1,5]又拆分为[1,3]sum9和[4,5]sum2[6,10]拆分为[6,8]sum13和[9,10]sum13以此类推直到叶子节点每个叶子节点对应数组的一个元素比如[1,1]sum5[2,2]sum1。从这个例子能看出线段树的构建过程就是不断分治拆区间而查询和修改就是沿着分治的路径合并或更新信息。三、线段树的构建从 0 到 1 搭建一棵区间树线段树的构建是递归分治的过程从根节点开始不断将区间拆分为左右子区间直到叶子节点单个元素再从叶子节点向上合并信息最终得到整棵线段树。3.1 构建的核心思路初始化当前节点的区间[l,r]如果是叶子节点lr则节点的信息等于原始数组对应位置的数值如果不是叶子节点计算区间中点mid(lr)/2递归构建左孩子[l,mid]和右孩子[mid1,r]左右孩子构建完成后向上合并信息pushup 操作当前节点的信息 左孩子信息 右孩子信息比如区间和的合并。3.2 代码实现构建维护区间和的线段树首先定义线段树的节点结构我们用结构体存储每个节点的左边界 l、右边界 r、区间和 sum再定义原始数组和线段树数组注意线段树数组开 4 倍大小。完整 C 代码框架#include iostream using namespace std; // 定义常数适配1e5级别的数据 #define N 100010 // 左孩子p*2右孩子p*21 #define lc p 1 #define rc p 1 | 1 // 用long long防止求和溢出 typedef long long LL; // 原始数组 LL a[N]; // 线段树节点l左边界r右边界sum区间和 struct Node { LL l, r, sum; } tr[N 2]; // 线段树数组开4倍 // 向上合并用左右孩子更新当前节点的信息 void pushup(int p) { tr[p].sum tr[lc].sum tr[rc].sum; } // 构建线段树p为当前节点编号l和r为当前节点维护的区间 void build(int p, int l, int r) { // 初始化当前节点的区间和sum tr[p] {l, r, 0}; // 叶子节点区间长度为1sum等于原始数组的值 if (l r) { tr[p].sum a[l]; return; } // 非叶子节点分治构建左右子树 int mid (l r) 1; // 等价于(lr)/2位运算更快 build(lc, l, mid); // 构建左孩子[l, mid] build(rc, mid 1, r); // 构建右孩子[mid1, r] // 合并左右孩子的sum更新当前节点 pushup(p); } int main() { int n; cin n; // 输入原始数组下标从1开始方便线段树操作 for (int i 1; i n; i) { cin a[i]; } // 构建线段树根节点编号为1维护区间[1, n] build(1, 1, n); return 0; }3.3 关键细节说明下标从 1 开始线段树的节点编号和数组下标都从 1 开始能避免处理 0 下标带来的左孩子 / 右孩子计算问题是算法竞赛中的通用写法pushup 操作这是线段树的核心操作之一专门用来向上合并孩子节点的信息后续的查询和修改都会用到。pushup 的逻辑根据维护的信息变化比如维护最大值的话pushup 就是tr[p].max max(tr[lc].max, tr[rc].max)数据类型求和时容易出现整数溢出因此用long long存储区间和这是新手最容易踩的坑时间复杂度线段树的构建过程遍历了所有节点总节点数约为2n因此时间复杂度为O(n)效率极高。四、线段树的区间查询拆分 拼凑快速求区间信息区间查询是线段树的核心功能之一比如查询[l,r]的和。其核心思路是拆分查询区间拼凑结果从根节点出发将查询区间拆分为线段树中若干个节点的区间这些节点的区间互不重叠且刚好覆盖查询区间将这些节点的信息合并就是查询结果。4.1 区间查询的核心规则假设当前节点维护的区间为[nodel​,noder​]要查询的区间为[ql​,qr​]递归查询的规则如下完全包含如果[nodel​,noder​]完全在[ql​,qr​]内直接返回当前节点的信息无需继续递归部分重叠如果[nodel​,noder​]和[ql​,qr​]部分重叠计算中点mid分别递归查询左孩子和右孩子只查询和查询区间有重叠的孩子最后合并左右孩子的查询结果无重叠如果[nodel​,noder​]和[ql​,qr​]无重叠返回无效值比如求和返回 0求最大值返回负无穷。4.2 举个例子查询[3,8]的和还是以数组a[5,1,3,0,2,2,7,4,5,8]的线段树为例查询[3,8]的和根节点[1,10]和[3,8]部分重叠中点mid5递归查询左孩子[1,5]和右孩子[6,10]左孩子[1,5]和[3,8]部分重叠中点mid3递归查询左孩子[1,3]和右孩子[4,5][1,3]和[3,8]部分重叠中点mid2递归查询右孩子[3,3]完全包含返回 sum3[4,5]完全包含在[3,8]内返回 sum2合并左孩子[1,5]的查询结果325右孩子[6,10]和[3,8]部分重叠中点mid8递归查询左孩子[6,8]完全包含返回 sum13和右孩子[9,10]无重叠返回 0合并右孩子[6,10]的查询结果13013合并根节点的查询结果51318即[3,8]的和为 18。从这个过程能看出查询的路径始终沿着树的层级向下不会遍历所有节点时间复杂度为O(logn)。4.3 代码实现区间和查询在之前构建代码的基础上添加区间查询的函数// 区间查询p为当前节点编号x和y为查询的区间[x, y] LL query(int p, int x, int y) { // 当前节点的区间 LL node_l tr[p].l, node_r tr[p].r; // 规则1完全包含直接返回当前节点的sum if (x node_l node_r y) { return tr[p].sum; } // 规则2部分重叠分治查询 LL res 0; // 求和的无效值为0 int mid (node_l node_r) 1; // 左孩子和查询区间有重叠查询左孩子 if (x mid) { res query(lc, x, y); } // 右孩子和查询区间有重叠查询右孩子 if (y mid) { res query(rc, x, y); } // 返回合并后的结果 return res; }4.4 测试代码构建 查询我们用一个简单的例子测试构建和查询功能int main() { // 测试数组a[1~5] [1,5,4,2,3] int n 5; a[1] 1, a[2] 5, a[3] 4, a[4] 2, a[5] 3; // 构建线段树 build(1, 1, 5); // 查询[2,5]的和542314 cout query(1, 2, 5) endl; // 查询[1,4]的和154212 cout query(1, 1, 4) endl; return 0; }输出结果14 12完全符合预期说明构建和查询的代码是正确的。五、线段树的单点修改更新叶子向上回溯单点修改指的是修改原始数组中某个位置的数值并同步更新线段树的信息。其核心思路是先递归找到对应位置的叶子节点修改叶子节点的信息再向上回溯更新所有路径上的节点信息因为这些节点的区间都包含该位置信息会受影响。5.1 单点修改的核心规则假设要修改原始数组中位置pos的数值增加k如果是替换为某个值可以先计算差值再执行增加操作递归修改的规则如下找到叶子节点如果当前节点是叶子节点lrpos直接修改节点的信息比如 sum k递归查找孩子如果不是叶子节点计算中点mid如果pos≤mid递归修改左孩子否则递归修改右孩子向上更新修改完孩子节点后调用 pushup 操作更新当前节点的信息直到回溯到根节点。5.2 举个例子将位置 6 的数增加 3还是以数组a[5,1,3,0,2,2,7,4,5,8]为例将位置 6 的数原值 2增加 3变为 5线段树的更新过程根节点[1,10]中点mid5pos65递归修改右孩子[6,10]节点[6,10]中点mid8pos68递归修改左孩子[6,8]节点[6,8]中点mid7pos67递归修改左孩子[6,7]节点[6,7]中点mid6pos66递归修改左孩子[6,6]叶子节点修改叶子节点[6,6]的 sum235然后向上回溯依次更新[6,7]、[6,8]、[6,10]、根节点[1,10]的 sum最终根节点的 sum 从 37 变为 40所有包含位置 6 的节点信息都完成了更新。5.3 代码实现单点修改在之前的代码基础上添加单点修改的函数支持将位置x的数值增加k// 单点修改p为当前节点编号x为要修改的位置k为增加的数值 void modify(int p, int x, LL k) { // 当前节点的区间 LL node_l tr[p].l, node_r tr[p].r; // 规则1找到叶子节点修改sum if (node_l x node_r x) { tr[p].sum k; return; } // 规则2分治查找要修改的孩子 int mid (node_l node_r) 1; if (x mid) { // 左孩子包含x修改左孩子 modify(lc, x, k); } else { // 右孩子包含x修改右孩子 modify(rc, x, k); } // 规则3向上更新当前节点的sum pushup(p); }5.4 实战洛谷 P3374 树状数组 1线段树解法链接https://www.luogu.com.cn/problem/P3374这是经典的单点修改 区间查询模板题我们用线段树来解决这道题检验我们的代码是否能应对实际问题。题目描述已知一个数列支持两种操作将第x个数加上k求区间[x,y]内所有数的和。输入输出示例输入5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4输出14 16完整 AC 代码#include iostream using namespace std; #define N 500010 #define lc p 1 #define rc p 1 | 1 typedef long long LL; LL a[N]; struct Node { LL l, r, sum; } tr[N 2]; void pushup(int p) { tr[p].sum tr[lc].sum tr[rc].sum; } void build(int p, int l, int r) { tr[p] {l, r, a[l]}; if (l r) return; int mid (l r) 1; build(lc, l, mid); build(rc, mid 1, r); pushup(p); } void modify(int p, int x, LL k) { LL l tr[p].l, r tr[p].r; if (l x r x) { tr[p].sum k; return; } int mid (l r) 1; if (x mid) modify(lc, x, k); else modify(rc, x, k); pushup(p); } LL query(int p, int x, int y) { LL l tr[p].l, r tr[p].r; if (x l r y) return tr[p].sum; LL sum 0; int mid (l r) 1; if (x mid) sum query(lc, x, y); if (y mid) sum query(rc, x, y); return sum; } int main() { ios::sync_with_stdio(false); cin.tie(0); // 加速cin避免超时 int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; } build(1, 1, n); while (m--) { int op, x, y; cin op x y; if (op 1) { // 单点修改第x个数加y modify(1, x, y); } else { // 区间查询[x,y]的和 cout query(1, x, y) endl; } } return 0; }代码说明添加了ios::sync_with_stdio(false); cin.tie(0);用来加速 C 的输入输出避免大数据量下的 cin 超时严格按照题目要求实现单点修改和区间查询代码和我们之前的讲解完全一致该代码能直接通过洛谷 P3374 的所有测试点说明我们的线段树入门代码是正确、高效的。总结线段树是算法竞赛中最常用、最强大的数据结构之一虽然入门有一定难度但只要理解了分治思想和节点信息的合并 / 更新逻辑后续的进阶内容都会水到渠成。学习线段树的关键是多敲代码、多做题目建议从基础的模板题开始比如洛谷 P3374、P1816手动实现构建、查询、修改的每一个步骤不要直接复制代码。当你能独立写出线段树的模板并理解每一行代码的含义时就算真正入门了后续我会继续更新线段树的进阶内容比如懒标记、区间修改、维护最大值等关注我一起从入门到精通线段树