1. 线段树算法竞赛中的“瑞士军刀”如果你参加过算法竞赛或者刷过一些在线评测平台比如力扣、洛谷、AcWing的题目一定对“区间问题”深恶痛绝。题目描述往往是这样的给你一个长度为 N 的数组然后有 M 次操作要么是修改某个区间里的所有值要么是查询某个区间的和、最大值、最小值等等。最朴素的想法每次修改就遍历区间每次查询也遍历区间时间复杂度是 O(N*M)数据量一大程序立刻就会超时。这时候你就需要一把“瑞士军刀”——线段树。我第一次接触线段树是在准备一场区域赛的时候被一道区间修改查询的题目卡了整整一个下午。用暴力方法写样例能过一提交就超时。后来学长指点说“这题得用线段树”我才开始硬着头皮去学。说实话刚开始看那些递归建树、区间查询的代码感觉头都大了完全不明白为什么要把简单的问题复杂化。但当我真正理解其思想并成功用线段树 AC 那道题后那种豁然开朗的感觉至今难忘。它就像是你工具箱里的一件多功能工具一旦掌握很多看似复杂的区间问题都能迎刃而解。简单来说线段树是一种基于分治思想的二叉树数据结构。它的核心目标就是用额外的空间通常是原数组的4倍来存储一些预处理好的信息从而将区间操作的时间复杂度从 O(N) 降为 O(log N)。你可以把它想象成公司里的管理层老板根节点管着整个公司整个数组他手下有两个经理左右子节点分别管着公司的前半部分和后半部分。每个经理手下又有自己的小团队如此层层划分直到最基层的员工叶子节点每个员工只负责一个具体的数据。当老板想知道公司这个月的总业绩区间和时他不需要去问每一个员工只需要问两个经理经理再去问自己的组长组长汇总后上报。这个“层层上报”的过程就是线段树的查询效率极高。在算法竞赛中线段树的应用场景极其广泛远不止求和求最值。从经典的区间加、区间乘到求区间的最大连续子段和、最大公约数再到高级的扫描线算法求矩形面积、解决一些复杂的计数和统计问题线段树都是核心的数据结构。可以说它是解决静态数组动态区间问题的首选利器。接下来我们就从最基础的原理开始一步步拆解这把“瑞士军刀”的每一个零件并直面竞赛中那些让人头疼的真题。2. 庖丁解牛线段树的原理与核心操作理解线段树关键在于理解它的“树形结构”和“递归思想”。很多新手会纠结于代码细节比如为什么节点数组要开4倍为什么查询函数要那样写其实只要把它的物理形态和逻辑流程想清楚代码就是水到渠成的事情。2.1 结构定义如何表示一个“区间节点”线段树的每个节点本质上代表原数组上的一个连续区间。我们需要在代码里定义这个节点的“身份证信息”。通常我们会用一个结构体来存储。struct Node { int l, r; // 节点所代表的区间左右端点 [l, r] int sum; // 这个区间我们需要维护的信息这里以“区间和”为例 // 还可以有其他信息比如 max最大值、min最小值、add懒标记等 } tr[N * 4]; // 存储所有节点的数组N是原数组长度开4倍空间是经验值这里有一个经典问题为什么数组要开4倍我当初也疑惑过。简单解释一下一棵线段树最坏情况下比如区间长度不是2的整数次幂它是一棵不完全二叉树。理论上的最大节点数会略少于 4N。开4倍是一个简单又安全的做法能保证绝对够用避免一些边界情况下的数组越界。你可以先记住这个结论在竞赛中无脑开4倍就行。2.2 建树Build从零搭建信息大厦有了结构我们就要把空荡荡的数组构建成一棵充满信息的树。这个过程是自顶向下递归的就像公司从老板开始搭建组织架构。// u: 当前节点在 tr 数组中的下标 // l, r: 当前节点需要管理的区间范围 void build(int u, int l, int r) { tr[u].l l, tr[u].r r; // 记录区间范围 if (l r) { // 到达叶子节点区间里只有一个元素 tr[u].sum w[l]; // w[] 是原始数组信息直接来自原数据 return; } // 不是叶子节点就继续分裂 int mid (l r) 1; // 取中点等价于 (l r) / 2 build(u 1, l, mid); // 递归构建左儿子下标是 u*2 build(u 1 | 1, mid 1, r); // 递归构建右儿子下标是 u*21 // 左右儿子都建好了用它们的信息来更新自己 pushup(u); }这里的u 1和u 1 | 1是位运算分别表示u*2和u*21这是二叉树中父子节点下标关系的常用技巧比直接乘除要快一点。pushup函数是线段树的灵魂操作之一它的作用就是用子节点的信息来更新父节点。void pushup(int u) { tr[u].sum tr[u 1].sum tr[u 1 | 1].sum; }看非常简单父节点的区间和等于两个儿子区间和相加。如果维护的是最大值这里就改成max操作。2.3 查询Query高效获取区间信息假设老板想知道销售部第3到第8个人的总业绩区间[3,8]的和。他不需要召集所有人流程是这样的老板问左经理管[1,5]和右经理管[6,10]。左经理发现自己的区间[1,5]只有一部分在[3,8]里于是他继续问自己的下属管[1,3]的组长和管[4,5]的组长。管[1,3]的组长发现自己的区间完全被[3,8]包含就直接上报自己的总和。管[4,5]的组长也是完全包含直接上报。右经理发现自己的区间[6,10]也部分被包含于是继续向下问… 最终所有“完全被查询区间包含”的节点直接贡献自己的值部分包含的则继续向下分裂询问。// u: 当前节点下标 // l, r: 想要查询的区间 int query(int u, int l, int r) { // 情况1当前节点管理的区间完全被查询区间包含 // 比如查询[3,8]当前节点是[4,5]那它的信息可以直接用不用再往下走了 if (tr[u].l l tr[u].r r) { return tr[u].sum; } // 情况2当前节点区间和查询区间有交集但不完全包含 // 需要分别向左右儿子询问 int mid (tr[u].l tr[u].r) 1; int res 0; if (l mid) { // 查询区间和左儿子有交集 res query(u 1, l, r); } if (r mid) { // 查询区间和右儿子有交集 res query(u 1 | 1, l, r); } return res; }这就是线段树查询的递归过程。由于每次递归区间长度大致减半所以查询的复杂度是 O(log N)。2.4 单点修改Modify更新基层员工数据如果某个员工的业绩变了比如原数组w[5]的值变了我们需要更新线段树。思路是从根节点出发找到代表那个点的叶子节点更新它然后回溯更新所有祖先节点的信息。// u: 当前节点下标 // x: 想要修改的原数组位置 // v: 想要修改成的值 void modify(int u, int x, int v) { if (tr[u].l tr[u].r) { // 找到叶子节点 tr[u].sum v; return; } // 根据x的位置决定去左子树还是右子树找 int mid (tr[u].l tr[u].r) 1; if (x mid) { modify(u 1, x, v); } else { modify(u 1 | 1, x, v); } // 儿子修改完了记得更新自己 pushup(u); }3. 化繁为简懒标记Lazy Propagation的精髓单点修改理解了但竞赛中更常见的是“区间修改”比如给区间[l, r]里的每个数都加上一个值d。如果还用单点修改的思路对区间内每个点都调用一次modify复杂度就退化成了 O(N log N)这比暴力 O(N) 还差显然不可接受。懒标记Lazy Tag就是为了解决这个问题而生的它是线段树最精妙也最难理解的部分。我把它叫做“领导的艺术”老板根节点接到一个任务“给销售部所有人加薪1000元”。高效的老板不会立刻打电话给每一个员工他会把这个任务记在自己的小本本上打上懒标记然后就去忙别的了。只有当需要查询某个销售小组的具体薪资时老板才会把本子上的任务交代给那个小组的经理下传标记经理再根据需要继续下传。这样修改的负担被延迟到了真正需要的时候才执行避免了大量无意义的即时更新。3.1 懒标记的实现我们需要在节点结构体里增加一个add成员用来记录“这个区间里的每个数都需要加上但还没加的值”。struct Node { int l, r; int sum; // 区间和 int add; // 懒标记表示该区间每个数待加的值 } tr[N * 4];核心是三个函数pushdown下传标记、带懒标记的modify区间修改和query区间查询。pushdown操作void pushdown(int u) { Node root tr[u], left tr[u 1], right tr[u 1 | 1]; if (root.add) { // 如果当前节点有未下传的标记 // 1. 将标记下传给左儿子 left.add root.add; left.sum (LL)(left.r - left.l 1) * root.add; // 更新左儿子的区间和 // 2. 将标记下传给右儿子 right.add root.add; right.sum (LL)(right.r - right.l 1) * root.add; // 3. 清空当前节点的标记任务已交代下去 root.add 0; } }注意更新子节点的sum时是区间长度 * 增加值。这里用(LL)强制转换是为了防止乘法溢出。带懒标记的区间修改// 给区间 [l, r] 里的每个数都加上 d void modify(int u, int l, int r, int d) { // 情况1当前节点区间完全被修改区间包含 if (l tr[u].l tr[u].r r) { // 直接更新当前节点的信息并打上懒标记 tr[u].sum (LL)(tr[u].r - tr[u].l 1) * d; tr[u].add d; return; // 不再往下递归 } // 情况2当前节点区间与修改区间部分重叠 // 在访问子节点之前必须先把当前节点的懒标记下传 pushdown(u); int mid (tr[u].l tr[u].r) 1; if (l mid) modify(u 1, l, r, d); // 修改涉及左儿子 if (r mid) modify(u 1 | 1, l, r, d); // 修改涉及右儿子 // 修改完儿子后更新自己的信息 pushup(u); }关键点在于如果当前区间被完全覆盖就就地更新并打标记然后返回不再深入。这保证了修改操作的时间复杂度也是 O(log N)。带懒标记的区间查询查询函数也需要修改因为在查询路径上如果遇到有懒标记的节点必须先把标记下传才能保证子节点的信息是正确的。LL query(int u, int l, int r) { if (l tr[u].l tr[u].r r) { return tr[u].sum; } // 与修改同理在访问子节点前下传懒标记 pushdown(u); int mid (tr[u].l tr[u].r) 1; LL res 0; if (l mid) res query(u 1, l, r); if (r mid) res query(u 1 | 1, l, r); return res; }3.2 更复杂的懒标记区间加乘混合运算有些题目更刁钻比如“先给区间乘一个数再加一个数”。这时懒标记就需要两个add加标记和mul乘标记。这里有一个至关重要的顺序问题必须先乘后加。为什么假设一个节点的值是x我们先给它打上(mulm, adda)的标记意思是要计算x * m a。如果再来一个操作(muln, addb)那么新的值应该是(x * m a) * n b x * (m*n) (a*n b)。所以合并标记的规则是新的乘法标记mul mul * n新的加法标记add add * n b在pushdown时更新子节点的公式也是子节点值 子节点值 * 父节点mul 父节点add * 子节点区间长度。这个顺序如果搞反结果就会出错是竞赛中常见的坑点。4. 实战拆解从模板题到竞赛真题懂了原理和模板不代表会做题。线段树的难点在于如何根据具体问题设计每个节点需要维护的信息以及如何写出正确的pushup和pushdown逻辑。下面我们通过几道经典和最新的竞赛题来感受一下。4.1 经典入门最大数洛谷 P1198这是一道非常好的单点修改区间查询最值的入门题。题目模拟一个序列支持两种操作A t在序列末尾添加一个数(t last) % p其中last是上次查询的结果。Q L查询序列最后L个数的最大值。解题思路因为最多有M次操作我们可以预先建立一个长度为M的空线段树。节点维护的信息很简单区间最大值v。添加操作就是单点修改在当前位置n1上修改值为((LL)t last) % p。查询操作就是区间查询查询区间[n - L 1, n]的最大值。这道题几乎就是线段树模板的直接应用但它巧妙地结合了“动态末尾添加”和“查询最后L个”考察了对单点修改和区间查询最值的理解。代码在原始文章中已经给出核心就是modify和query函数中把sum换成max操作。4.2 进阶挑战区间最大连续子段和AcWing 245这道题要求我们维护一个序列支持单点修改和查询区间内的最大连续子段和。这是线段树维护复杂信息的经典例题。如果只维护区间和sum我们无法通过左右儿子的信息快速得到父区间的最大连续子段和。因此我们需要为每个节点维护四个信息sum: 区间和。lmax: 区间最大前缀和必须包含左端点。rmax: 区间最大后缀和必须包含右端点。tmax: 区间最大连续子段和就是我们最终要查询的。关键在于pushup函数如何用左右儿子l和r的信息合并出父节点u的信息u.sum l.sum r.sum。这个简单。u.lmax max(l.lmax, l.sum r.lmax)。父区间的最大前缀和要么完全在左儿子里要么跨越左右儿子左儿子全取 右儿子的最大前缀。u.rmax max(r.rmax, r.sum l.rmax)。同理父区间的最大后缀和要么完全在右儿子里要么跨越左右儿子右儿子全取 左儿子的最大后缀。u.tmax max( max(l.tmax, r.tmax), l.rmax r.lmax)。父区间的最大连续子段和有三种可能完全在左儿子内部、完全在右儿子内部、或者横跨左右儿子左儿子的最大后缀 右儿子的最大前缀。想通了这个合并逻辑这道题就解决了大半。剩下的单点修改和区间查询框架和基础线段树一样只是在回溯时调用这个自定义的pushup即可。这种“维护多个信息并通过特定规则合并”的思想是解决线段树难题的关键。4.3 竞赛真题剖析拼十字问题蓝桥杯 2024我们来看一道较新的真题它展示了线段树如何应用于计数问题。题目大意有n个矩形每个矩形有长度l、宽度w和颜色c三种颜色之一。要求统计有多少对矩形可以拼成一个“十字形”即一个矩形竖放作为主干另一个不同颜色的矩形横放作为横梁且横梁矩形的长度要严格小于主干矩形的长度宽度要严格小于主干矩形的宽度。暴力思路是O(n²)枚举所有矩形对判断条件显然超时。线段树优化思路排序将所有矩形按长度l从大到小排序。这样当我们顺序处理矩形时当前矩形作为“主干”候选之前处理过的矩形长度更大或相等才有可能作为它的“横梁”因为要求横梁长度l_t 主干长度l_m。由于我们从大到小处理之前处理过的矩形长度都大于等于当前矩形我们需要的是严格小于所以对于长度相同的矩形需要特殊处理通常把宽度小的放前面避免同长度矩形被误计。数据结构我们需要快速查询在已经处理过的矩形中有多少个矩形其颜色与当前矩形不同且宽度小于当前矩形宽度。线段树作用建立三棵线段树或一棵维护结构体的树分别维护三种颜色的矩形。每棵线段树的下标是宽度值域树中存储的是“当前已处理的、属于该颜色的、宽度为某个值的矩形有多少个”。流程从长度最大的矩形开始处理。对于当前矩形颜色为c宽度为w我们需要查询其他两种颜色的线段树中宽度在[1, w-1]区间内的矩形总数。这个查询就是线段树的区间求和查询query(1, 1, w-1)。将查询结果累加到答案中。然后将当前矩形插入到它所属颜色的线段树中即执行modify(1, w, 1)宽度w的位置计数1。为什么可行因为我们按长度从大到小处理所以当处理到当前矩形时线段树里存放的都是长度大于它的矩形同长度且已处理的其宽度一定更小不会作为它的横梁符合要求。我们通过宽度查询直接筛选出了所有可能的“横梁”矩形。颜色不同的要求通过维护三棵独立的树来实现。这道题将线段树从“维护数值”提升到了“维护计数”并结合排序技巧将二维偏序问题长度、宽度转化为了可以通过一维数据结构以宽度为下标快速求解的问题。它充分考察了选手的问题转化能力和数据结构应用能力。5. 避坑指南与高阶技巧在实战中除了理解原理还有很多细节和技巧能帮你节省时间、避免错误。5.1 常见“坑点”与调试技巧数组大小这是最常犯的错误之一。线段树节点数组要开4倍原数组大小。如果用了懒标记或者维护了多个信息结构体里的数组也要相应开够。数据类型溢出这是第二常见的错误。区间和、区间乘法的结果很可能超出int范围。在定义sum、add、mul等变量时要养成习惯用long long。在pushdown和pushup中进行乘法运算时也要注意加上(LL)强制转换。懒标记初始化建树时加法标记add要初始化为0乘法标记mul要初始化为1。我曾在一次比赛中因为mul忘记初始化为1导致调试了半个小时。pushdown的时机只有在需要访问当前节点的子节点时才需要下传懒标记。即在modify和query函数中当当前区间没有被完全覆盖需要递归访问子节点之前必须调用pushdown。很多新手会在函数开头就pushdown这是不必要的。边界条件查询区间[l, r]要确保l r。在递归时判断与子区间是否有交集的条件l mid和r mid要写对。调试技巧打印线段树写一个简单的print函数按层打印每个节点的区间[l, r]和其维护的信息sum,max,add等。这对于检查建树和修改操作是否正确非常有效。小数据模拟用纸笔模拟一个长度很小比如4或5的数组手动执行一遍建树、修改、查询的过程再与程序输出对比。对拍写一个暴力算法时间复杂度高但保证正确用随机生成的数据同时运行你的线段树程序和暴力程序比较结果是否一致。这是竞赛中验证正确性的终极法宝。5.2 高阶技巧动态开点与权值线段树前面我们用的都是“静态”线段树需要预先知道值域并开好4倍数组。但如果值域非常大比如[1, 1e9]而实际操作次数M却不多比如1e5次开4倍数组会导致内存爆炸。这时就需要动态开点线段树。它的思想是“用时再创建”不再用数组下标u*2和u*21来定位儿子而是为每个节点显式记录左右儿子的指针或索引。只有当一个节点被用到时我们才为它分配空间。这样总节点数大约为O(M log N)大大节省了空间。动态开点线段树的代码结构会有所不同但核心思想pushup,pushdown,modify,query完全不变。权值线段树是动态开点线段树的一个典型应用。它的“下标”不再是数组的位置而是数值本身。节点维护的信息通常是“这个值出现了多少次”。它可以高效解决“求第k小的数”、“求某个值的排名”、“求前驱后继”等问题是平衡树的一种替代实现代码往往更简单。5.3 思维提升何时该想到线段树经过大量练习你会形成一种直觉。当你看到题目具有以下特征时就应该考虑线段树数据范围数组长度N和操作次数M通常在1e5到1e6级别要求时间复杂度在O(N log N)或O(M log N)。操作类型核心操作是“区间修改”加、乘、赋值等和“区间查询”和、最值、GCD、某种统计信息。问题特征问题可以转化为对序列区间属性的维护和询问。即使题目背景是二维的如矩形面积并、树上的如树链剖分其本质往往也是将问题映射到一维序列上用线段树解决。线段树的学习曲线比较陡峭但一旦跨越你会发现自己解决区间问题的能力有了质的飞跃。它不仅仅是模板更是一种分治和信息合并的思维方式。多做题多总结从模仿模板开始到独立设计节点信息最终你会发现自己能够灵活运用这把“瑞士军刀”去拆解竞赛场上的各种难题。记住所有复杂的代码都是由简单的逻辑一层层组合而成的。从理解每一个pushup和pushdown开始你的算法功力就在稳步提升。