简介线段树是程序设计竞赛中处理区间查询与修改的高效数据结构特别适合区间求和、最值、乘积、异或等聚合操作的大规模数据场景。这份PDF以竞赛实战为背景系统梳理线段树的重要性、作用、二叉树原理与懒标记机制详述节点结构、建树、单点修改、区间修改、单点查询、区间查询等核心函数的C实现并配合例题逐层拆解从朴素O(nm)到O(log n)的复杂度优化帮助读者理解区间更新与回溯细节规避超时陷阱。资源共1个文件PDF格式压缩包大小约1.69MB内容聚焦、结构清晰、代码示例可直接对照学习可作为ACM、蓝桥杯等算法竞赛选手及初学者的专业参考文献。目前已有92人学习下载尤其适合需要快速掌握线段树区间操作、提升竞赛解题效率的学生阅读。1. 线段树在程序设计竞赛里到底解决什么问题模拟赛里有一道区间染色题数组长度 1e5操作数 1e5用朴素循环改边界最后一组数据跑了 2 秒多把线段树模板换上去同一份数据降到 0.3 秒。这不是常数优化带来的差异而是单次区间操作从 O(n) 变成 O(log n) 的结果。程序设计竞赛中的线段树问题研究的核心就是这类动态区间模型数组可以在线修改区间可以随时查询每个操作都必须在几十毫秒内给出答案。线段树把区间求和、区间最值、区间 gcd 合并成同一套树形结构按需替换合并函数即可。竞赛语境下说“研究”线段树问题不是做学术证明而是要能快速判断一道题该用哪种线段树、延迟标记什么时候会冲突、空间开多少不出错。这篇文章写给准备区域赛的选手和带队的教练默认读者会写数组模拟但没有系统整理过线段树的边界条件。2. 线段树的静态结构与竞赛中的四倍空间约束2.1 递归分治让线段树的结构一眼可读线段树的每个节点对应一段连续区间根节点负责整个数组叶子节点负责单个元素内部节点把自己管理的区间从中间切成两半交给左右两个孩子。竞赛里我一般不用结构体指针建树而是用一个整型下标 p 表示节点根节点下标固定为 1左孩子是 p*2右孩子是 p*21。这样整棵树可以直接放进一维静态数组不需要 new不需要管理左右孩子指针回溯时把两个孩子的信息合并回当前节点就行。这个约定也叫完全二叉树下标法。递归进入节点时带上区间边界 l、r中点 m (l r) / 2左孩子管 [l, m]右孩子管 [m1, r]只要 l ! r 就继续往下拆。递归写法在建树、单点修改、区间查询三段代码里共享同一个下标规则出错率比手写迭代版本低很多。迭代线段树常数更小但需要额外处理层内偏移和哨兵节点比赛时心智负担重我优先保证正确性而不是在 1e5 数据量上追求那点常数差距。const int MAXN 100000; int n, tree[4 * MAXN 5]; void build(int p, int l, int r, int a[]) { if (l r) { // 叶子节点只存一个位置的值 tree[p] a[l]; return; } int m (l r) / 2; build(p * 2, l, m, a); // 左半边 build(p * 2 1, m 1, r, a); // 右半边 tree[p] max(tree[p * 2], tree[p * 2 1]); // 回溯合并 }参数 p 是当前节点在一维数组里的存储下标l、r 是它管辖的数组区间。调用时从 build(1, 1, n, a) 进入第一个参数必须是 1否则整棵树的父子下标关系全部错位。合并行写在递归返回之后保证当前节点的信息一定来自已经建好的两个孩子。如果题目求的是区间和把 max 换成加号求 gcd 就换成 gcd 函数。2.2 两倍空间不够一个 n6 的反例很多选手凭直觉给 tree 开 2n结果在 n6 这种数据上就越界。递归过程中叶子节点不一定会落在连续区间里根节点下标 1 管理 [1,6]切出 [1,3] 和 [4,6]左边继续切 [1,2] 和 [3,3]右边切 [4,5] 和 [6,6]这里已经用到了下标 7再把 [1,2] 拆成 8、9把 [4,5] 拆成 12、13最终访问到的最大下标是 13而 2n 只有 12。n递归建树访问到的最大节点下标2n4n3561261312247131428100000小于 400000200000400000下标跳跃的幅度和数组长度奇偶有关无法给出一个比 4n 更紧凑且对所有 n 都成立的静态上界所以竞赛现场统一开 4n5。n1e5 时 tree 数组大小约 40 万int 占用约 1.6 MB即使同时维护 tree 和 lazy 两个数组也只有 3.2 MB内存限制 256 MB 的题目随便开。2.3 建树参数与合并函数的替换规则线段树的合并函数决定了这棵树能回答什么问题。求区间和时合并行是 tree[p] tree[p*2] tree[p*21]求区间最小值把 max 改成 min维护最大子段和时每个节点需要额外存前缀最大和后缀最大合并逻辑会变复杂但树形框架不变。提示建树的时间复杂度是 O(n)。整棵树最多有 2n-1 个节点每个节点只做一次 O(1) 合并这和后面每次查询 O(log n) 的复杂度是独立的不要因为建树只跑一次就随便写。3. 单点更新与区间查询竞赛线段树的高频操作组合3.1 查询区间时的三态裁剪规则查询 [ql, qr] 时当前节点 [l, r] 只有三种状态与查询区间完全不交直接返回空值完全被查询区间包含直接返回 tree[p]部分重叠就递归进入两个孩子把两边结果合并后返回。这个分支逻辑是整个查询函数的主体写对三个分支查询就成功了一半。部分重叠的判断细节值得多说一句不要写成同时满足 ql l 和 qr r 就递归两边正确做法是分别判断 ql m 和 qr m。这样保证每次递归只进入与查询区间有交集的子树单次查询访问的节点数是 O(log n)。完全不交的情况在递归入口不会显式出现它是通过 if 条件天然过滤掉的。空值选择是最容易踩的坑。求最大值时空值不能用 0测试数据里元素可能全是负数0 会把正确结果刷新掉我一般用 -2e9或者 INT_MIN / 2。求最小值用 2e9求区间和时空值取 0求 gcd 时空值取 0求最大子段和时空值处理又不同每个语义都要单独检查。3.2 单点修改自顶向下定位叶子单点修改的思路比查询简单从根节点出发根据 pos 和当前节点中点 m 的大小关系选择进入左孩子或右孩子走到叶子后直接改写值然后原路回溯把经过的每个节点的 tree[p] 重新合并一遍。因为路径长度等于树高单次修改只访问 O(log n) 个节点。这套逻辑里唯一需要操心的是回溯时的合并顺序。叶子修改完必须一层一层往上更新否则根节点拿到的还是旧值。有些选手先改叶子再回溯时忘了合并导致后续查询一直读到旧信息这是线段树题里最常见的“对拍才能发现”的错误。3.3 一个可以直接上场的最大值模板#include bits/stdc.h using namespace std; const int MAXN 100000; int tree[4 * MAXN 5]; void build(int p, int l, int r, int a[]) { if (l r) { tree[p] a[l]; return; } int m (l r) / 2; build(p * 2, l, m, a); build(p * 2 1, m 1, r, a); tree[p] max(tree[p * 2], tree[p * 2 1]); } void modify(int p, int l, int r, int pos, int val) { if (l r) { // 找到目标叶子 tree[p] val; return; } int m (l r) / 2; if (pos m) modify(p * 2, l, m, pos, val); // 目标在左半 else modify(p * 2 1, m 1, r, pos, val); // 目标在右半 tree[p] max(tree[p * 2], tree[p * 2 1]); // 回溯合并 } int query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tree[p]; // 完全覆盖 int m (l r) / 2; int res -2000000000; if (ql m) res max(res, query(p * 2, l, m, ql, qr)); if (qr m) res max(res, query(p * 2 1, m 1, r, ql, qr)); return res; } int main() { int n 5, a[6] {0, 1, 3, 5, 7, 9}; build(1, 1, n, a); printf(%d\n, query(1, 1, n, 2, 4)); // 输出 7 modify(1, 1, n, 3, 8); printf(%d\n, query(1, 1, n, 2, 4)); // 输出 8 return 0; }代码里的 res 初始化为极小值保证第一次 max 一定被查询到的真实节点值覆盖。query 的两个 if 分别对应进入左子树和右子树的条件如果目标区间只落在左半右半的 if 不成立不会发生无效递归。modify 里 pos m 进左孩子否则进右孩子定位到叶子后 return回溯时所有祖先节点的 max 值都会重新计算。操作调用方式复杂度返回语义建树build(1, 1, n, a)O(n)无单点修改modify(1, 1, n, pos, val)O(log n)无区间查询query(1, 1, n, ql, qr)O(log n)[ql, qr] 的最大值3.4 查询端点和返回值的边界约定线段树的下标在代码里默认从 1 开始数组 a 的 0 号位置闲置。如果题目给的是 0-based 数组我习惯把它整体偏移一位而不是改线段树的区间逻辑因为当前递归写法里所有判断都是围绕闭区间设计的改成 [0, n-1] 后 m 的计算和边界判断都要跟着变容易出问题。查询时 ql 和 qr 必须满足 ql qr。如果 ql qr递归条件会全部失配返回 res 初始值这个结果没有任何意义。数据生成器里的区间端点一般不会反着出但手写对拍脚本时容易被忽略。此类模板能处理的数据规模在 n 和操作数都到 2e5 时依然稳定递归深度约等于 log2(n)不会爆栈。等需要维护区间和达到 1e9 级别时tree 的存储类型要换成 long long这个在第 4 章的延迟标记里更要提前注意。4. 延迟标记线段树从“单点改”升级为“区间改”的转折点4.1 朴素区间更新的复杂度灾难如果沿用单点修改的思路做区间更新把 [ql, qr] 里每个位置分别 modify 一次最坏情况下一次全区间更新要碰 n 个叶子每个叶子的祖先都要重新合并复杂度是 O(n log n)。操作数达到 1e5 时总操作量约 1e11 次访问任何常数优化都救不回来。更新方案一次全区间更新的复杂度1e5 次全区间更新的估算操作量逐点 modifyO(n log n)约 1e11更新到完全覆盖节点就停O(1)约 1e5延迟标记配合部分覆盖更新O(log n)约 1.7e6竞赛题里区间更新几乎不会只做全区间更多是随机区间比如“把 [l, r] 每个数加 v”。这类操作的共同点是被更新区间可能和节点区间完全重合也可能只压住节点区间的一部分。延迟标记解决的就是后一种情况。4.2 lazy 标记的含义与 pushdown 时机延迟标记的核心思想是当更新区间完全覆盖当前节点时只更新当前节点的 sum 和 lazy不递归进子树。这样一次区间更新可能落在多个节点上每个节点都是 O(1) 修改总访问量 O(log n) 个节点。后续一旦有查询或更新需要进入某个带标记节点的子树就必须先把标记下推给孩子否则孩子节点的值仍是旧数据。pushdown 里的操作顺序要注意先判断 lazy[p] 是否为 0为 0 直接返回避免不必要的乘法运算然后把当前标记加到两个孩子节点上同时更新孩子的 tree 值最后把自己的 lazy 清空。叶子节点不用下推因为叶子没有子树lazy 数组里对应的值永远不会被读取。void pushdown(int p, int l, int r) { if (lazy[p] 0 || l r) return; int m (l r) / 2; tree[p * 2] lazy[p] * (m - l 1); // 左孩子区间长度 lazy[p * 2] lazy[p]; tree[p * 2 1] lazy[p] * (r - m); // 右孩子区间长度 lazy[p * 2 1] lazy[p]; lazy[p] 0; }这里 tree 存的是区间和所以下推时给左孩子加的值是 lazy[p] 乘以左孩子管理的元素个数右孩子同理。如果线段树维护的是区间最大值下推时应该写成 tree[p*2] lazy[p]因为最大值只需要加一次标记值不需要乘区间长度。4.3 带延迟标记的区间加与区间求和模板const int MAXN 100000; long long tree[4 * MAXN 5], lazy[4 * MAXN 5]; void build(int p, int l, int r, int a[]) { if (l r) { tree[p] a[l]; return; } int m (l r) / 2; build(p * 2, l, m, a); build(p * 2 1, m 1, r, a); tree[p] tree[p * 2] tree[p * 2 1]; // 区间和合并 } void update(int p, int l, int r, int ql, int qr, long long v) { if (ql l r qr) { // 完全覆盖标记停留在这里 tree[p] v * (r - l 1); lazy[p] v; return; } pushdown(p, l, r); // 部分覆盖先处理历史标记 int m (l r) / 2; if (ql m) update(p * 2, l, m, ql, qr, v); if (qr m) update(p * 2 1, m 1, r, ql, qr, v); tree[p] tree[p * 2] tree[p * 2 1]; } long long querySum(int p, int l, int r, int ql, int qr) { if (ql l r qr) return tree[p]; pushdown(p, l, r); // 查询也要先下推 int m (l r) / 2; long long res 0; if (ql m) res querySum(p * 2, l, m, ql, qr); if (qr m) res querySum(p * 2 1, m 1, r, ql, qr); return res; }update 函数里完全覆盖分支是整个算法的关键它不递归只改当前节点和自己累加的 lazy。修改完成后部分覆盖的祖先节点仍要从两个孩子重新合并保证 tree 代表最新状态。querySum 里必须调用 pushdown因为查询可能进入带标记的子区间如果不下推孩子节点的 tree 值缺少原始区间加号。提示区间更新的值 v 类型是 long long。当 n1e5、操作次数 1e5、单次加值 1e9 时区间和最大可达 1e19远超 int 上限。tree 和 lazy 必须同时用 long long否则累加溢出很难排查。4.4 加法和乘法混合标记合并的顺序不能搞反区域赛里常见“区间加、区间乘、区间求和”三合一操作这类题不能只存一个 lazy 加法标记要维护二元组 (mul, add)表示某个节点的真实值等于原值乘 mul 再加 add。两个关键规则区间乘 k当前节点 tree 乘 kmul 乘 kadd 也乘 k区间加 ktree 加 k 乘区间长度add 加 kmul 不变。如果处理顺序反了比如先给 add 乘 k 再算乘法乘法的结果会多出一层加法误差。pushdown 时同样按这个顺序把标记下推给孩子先处理乘法再处理加法。赋值标记属于另一类操作无法用 (mul, add) 表达必须单独设一个状态位竞赛题里同时出现赋值和加乘时优先检查这一步。5. 线段树的题目识别与对拍考场收尾的两个动作5.1 三个信号决定要不要套线段树读完题先别急着写看题目描述是否同时包含三个信号。第一是动态修改存在“每次操作把区间内所有元素加上某个数”这类语句第二是区间查询询问的对象是 [l, r] 范围内的最大值、和或其他可合并信息第三是修改与查询交错数据范围到 1e5 以上。三个条件同时满足时线段树基本是正解方向之一。信号典型描述出现但不用线段树的场景动态修改区间元素整体变化只有单点改树状数组可解区间查询查询 [l, r] 的最大值静态区间可用 ST 表可合并语义最大子段和、区间 gcd操作为差分求前缀和如果题目只是静态数组加多组前缀和询问用前缀和数组 O(1) 就能回答没必要上线段树如果只有一个单点改和区间最大值查询树状数组维护 max 也能做但代码比线段树短。线段树的优势在于同时支持区间更新和多种合并语义尤其当 BIT 无法维护最大值或最大子段和时线段树几乎是唯一选择。5.2 用对拍验证模板而不是直接交第一版每次重写线段树模板后我先跑随机对拍再上赛场这是成本最低的验证方式。对拍需要三样东西一个输出正确答案的暴力程序一个套线段树的程序一个生成随机测试数据的脚本。暴力程序维护普通数组遇到查询就循环扫区间遇到修改就逐点更新结果一定正确但复杂度高只用来生成小数据时的标准输出。#!/bin/bash for i in $(seq 1 500); do python3 gen.py in.txt ./brute in.txt out_brute.txt ./seg in.txt out_seg.txt if ! cmp -s out_brute.txt out_seg.txt; then echo mismatch at case $i break fi done# gen.py import random random.seed() n random.randint(2, 20) q 30 print(n) print(q) for _ in range(q): typ random.randrange(2) l random.randint(1, n) r random.randint(l, n) if typ 0: print(Q, l, r) else: print(M, l, r, random.randint(-10, 10))对拍脚本里最关键的是生成器要覆盖边界区间端点 l 和 r 必须保证 l r修改值包含负数和零数组长度从 2 到 20 随机取。cmp 检测到第一处不同就停止接着把 gen.py 里 randint(2, 20) 改成 randint(1, 100000)再跑第二轮验证大数据下没有运行错误。随机对拍通过后再补一组手工边界所有区间端点固定取 1、n、n/2、n/21连续跑五次重点检查 n 为偶数时中点两侧的区间划分是否正确。能通过这组用例模板基本可以信任。本文还有配套的精品资源点击获取