每年蓝桥杯省赛结束总有人跟我复盘区间和的题明明知道该用前缀和一紧张把下标写错了区间更新的题明明知道用差分却忘了开 long long坐标范围 1e9 的题想破头也没想到离散化。说实话这三样东西单独拎出来任何一个学过基础算法的人都会但放在蓝桥杯真题里它们往往是组合出现的。前缀和解决静态区间求和差分解决区间批量更新离散化解决坐标过大问题合在一起几乎能覆盖竞赛里一大半“区间统计”类场景。这篇文章就把它们彻底讲透再给一条我自己在备赛实战里反复验证过的刷题路线。1. 为什么前缀和、差分、离散化是蓝桥杯的“必争之地”1.1 赛题中的出现频率与考察形式蓝桥杯省赛一般十道题左右Java B 组、C/C B 组、Python 组的考点重叠度非常高而区间问题几乎是每年的固定嘉宾。我统计过近几年的省赛和国赛题目前缀和和差分很少缺席。有的年份直接出“给定数组和多次区间查询”有的年份把差分藏在区间覆盖、染色、任务调度等包装后面还有的年份会在贪心、字符串、树状数组的题目前置一个离散化步骤。很多选手不是不会这些算法而是不知道什么时候该用或者用的时候边界没处理好导致整道题白写。离散化更特殊一些它不算是独立算法更像是一种空间压缩思路。蓝桥杯特别喜欢把数据范围拉到 1e9同时保证实际参与的坐标点数量只有 1e5 左右。这时候数组开不下直接开 Map 又慢又容易写乱离散化就是最优解。所以在我的备赛体系里这三者不是“会做模板题”就够的要能在一道综合题里识别出它们的痕迹并且能快速把模板写出来不占太多时间。1.2 三者的数学关系一条连续的技术链路先给出最核心的一句话前缀和是差分的前缀和差分是前缀和的差分二者互为逆运算离散化则是把稀疏的大值域坐标映射到连续的小下标让前缀和和差分可以派上用场。这个概念很关键。很多同学把前缀和当“区间求和工具”把差分当“区间更新工具”觉得它们是两套独立东西。但实际上差分数组做一次前缀和就能恢复出原数组前缀和数组做一次差分也能还原出原数组。这种互逆关系不止是数学上的对称更意味着你可以把差分和前缀和灵活组合先用差分把多次区间更新的增量记录下来最后一次前缀和还原就能得到所有更新叠加后的最终状态。这个“先差分再前缀和”的流水线是区间覆盖、区间统计类题目最常见的技术骨架。离散化刚好是这条流水线的前置步骤。真实比赛里的坐标往往不是连续的 1 到 n而是散布在 1 到 1e9 之间。直接拿这些大坐标做差分数组根本开不下。我们要做的就是把所有用到的坐标收集起来排序、去重、映射成 1 到 m 的连续小下标之后在这套小下标上跑差分和前缀和。所以你可以把三者的关系理解成离散化负责压缩地图差分负责在压缩后的地图上做区域标记前缀和负责把标记汇总成最终结果。1.3 快速判断该用哪个的速查表刷题和比赛时我习惯先判断题目属于哪类模型再动手写代码。这里给出一张我自己用得非常顺手的速查表题目特征首选算法时间复杂度静态数组多次询问区间和、子矩阵和前缀和预处理 O(n)单次查询 O(1)多次区间整体加/减最后求数组状态差分每次更新 O(1)还原 O(n)值域极大但用到的坐标点很少离散化排序去重 O(n log n)大坐标区间覆盖统计覆盖次数/覆盖长度离散化 差分 前缀和O((nm) log(nm))更新和查询交替出现需要在线回答树状数组 / 线段树每次操作 O(log n)注意最后一行。如果题目里更新和查询是交替出现的那就不能只用普通差分因为普通差分只支持所有更新做完之后再统一还原。遇到这种在线场景要升级到树状数组或者线段树。蓝桥杯里大部分区间更新题目都是“先把操作给完最后再查询”所以差分仍然是最高频的解法。2. 前缀和区间查询的加速引擎2.1 一维前缀和前因后果前缀和的定义很朴素设原数组 a[1..n]前缀和数组 s[i] 表示 a[1] 到 a[i] 的累加和。构造时用递推公式 s[i] s[i-1] a[i]查询区间 [l, r] 的累加和时直接用 s[r] - s[l-1]。关键前提是下标从 1 开始。我见过太多人在下标从 0 开始导致 s[l-1] 变成 s[-1] 的情况。蓝桥杯的题目描述里区间基本都是闭区间 [l, r]下标从 1 开始可以直接套公式不用去想“这里要不要加一减一”省下的时间足够再调试一个 bug。如果你是 Python 选手也建议用占位符 a [0] list(...) 的方式把下标整体右移一位。代码模板如下const int N 100005; long long a[N], s[N]; int n, q; cin n q; for (int i 1; i n; i) { cin a[i]; s[i] s[i - 1] a[i]; } while (q--) { int l, r; cin l r; cout s[r] - s[l - 1] \n; }Python 版本也很简洁n, q map(int, input().split()) a [0] list(map(int, input().split())) s [0] * (n 1) for i in range(1, n 1): s[i] s[i - 1] a[i] for _ in range(q): l, r map(int, input().split()) print(s[r] - s[l - 1])这里有两个高频坑。第一个是数据类型蓝桥杯的数组元素经常给到 1e9n 到 1e5区间累加和轻松超过 int 上限所以前缀和数组和最终结果必须用 long long。这个问题在 C/C 里尤其要警惕Java 里对应 longPython 则不用担心。第二个是读入优化C 建议关掉同步流Java 用 BufferedReaderPython 用 sys.stdin.buffer.read 一次性读入否则数据量大时可能超时。2.2 二维前缀和容斥原理是核心二维前缀和解决的是子矩阵求和问题。给一个 n 行 m 列的矩阵q 次询问每次求左上角 (x1, y1) 到右下角 (x2, y2) 这个子矩阵的所有元素之和。暴力做法每次 O(n*m)大概率超时。二维前缀和能把单次查询压到 O(1)。预处理公式pre[i][j] a[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]这个公式的推导用到了容斥原理。pre[i][j] 表示左上角 (1,1) 到 (i,j) 这个大矩形的总和。它等于当前格子的值加上上方矩形的总和、左边矩形的总和但左上角那个小矩形被加了两次所以要减掉一次。查询公式sum pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]画个图看更清晰本质上还是容斥。用 pre[x2][y2] 这个大矩形减去上方一块、左方一块但左上角那块被减了两次再加回来一次。代码模板for (int i 1; i n; i) for (int j 1; j m; j) { cin a[i][j]; pre[i][j] a[i][j] pre[i - 1][j] pre[i][j - 1] - pre[i - 1][j - 1]; } int x1, y1, x2, y2; cin x1 y1 x2 y2; long long res pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] pre[x1 - 1][y1 - 1];二维前缀和的代码本身不难难在下标。你永远要记得 x1-1、y1-1 这些边界一旦某个地方写漏就整题报废。我习惯在写完代码后专门用一组包含边界值的样例来验证比如查询整个矩阵、查询第一行第一列、查询单个格子三个样例能覆盖大部分下标错误。2.3 前缀和的衍生用法异或前缀和与哈希配合前缀和思想可以推广到其它满足区间可减性的运算。最典型的是异或前缀和处理区间异或查询。求 [l, r] 的异或值时预处理 xor[i] xor[i-1] ^ a[i]查询用 xor[r] ^ xor[l-1]。因为异或自己会抵消所以区间异或和前缀异或之间的关系跟区间和一模一样只是“减”变成了“异或”。更进阶的套路是“前缀和 哈希表”在蓝桥杯里也考过。典型题给定数组求有多少个连续子数组的和为 k。暴力枚举子数组是 O(n^2)用前缀和后转化为“找 ijs[j] - s[i] k”也就是“找 s[i] s[j] - k”。用一个哈希表记录每个前缀和出现过的次数从左到右扫一遍即可复杂度降到 O(n)。这个套路解决“和为 k 的子数组”、“和能被 k 整除的子数组”都非常有效。2.4 前缀和的最大子段和用法优化最大子段和是一个经典问题要求在一个数组里找一段连续子数组使它的和最大。朴素枚举所有端点需要 O(n^2)但利用前缀和可以设计出 O(n) 的动态规划。设 dp[i] 表示以 a[i] 结尾的最大子段和状态转移为 dp[i] max(a[i], dp[i-1] a[i])最终答案就是 max(dp[i])。你可能觉得这跟前缀和没关系但换个角度看以 i 结尾的最大子段和本质上是在找最小的前缀和 s[j]j i然后用 s[i] - s[j] 来最大化区间和。于是就有了另一个等价解法从左往右遍历前缀和维护历史最小前缀和每一步更新答案。这种方法在后面遇到“区间和尽可能大/小”的题目时可以灵活迁移。3. 差分区间更新的 O(1) 利器3.1 差分数组的构造与还原逻辑差分数组 d[i] 的定义是原数组相邻两项之差d[i] a[i] - a[i-1]。你会发现对差分数组 d 做一次前缀和就能还原出 a[i]也就是 d[1] d[2] ... d[i] a[i]。这个性质是差分解决区间更新问题的基础。考虑一个操作把闭区间 [l, r] 内的所有元素都加上 v。如果直接遍历区间最坏 O(n)m 次操作下来 O(n*m) 直接爆炸。但如果用差分数组只需要两条语句d[l] v; d[r 1] - v;所有更新做完后对 d 数组做一次前缀和就能得到最终数组。原理是差分前缀和还原时d[l] 的 v 会持续影响到后面每一个位置直到 r1 处被减掉于是只有 [l, r] 内的元素被加上了 v。这就是区间更新的 O(1) 加速。模板非常简单int n, m; cin n m; vectorlong long d(n 2, 0); // 多开一个位置避免 r1 越界 while (m--) { int l, r; long long v; cin l r v; d[l] v; d[r 1] - v; } for (int i 1; i n; i) { d[i] d[i - 1]; cout d[i] (i n ? \n : ); }这里有一个极其重要的习惯差分数组要开成 n2不是 n1。因为当 r n 时需要访问 d[r1] d[n1]如果数组只开到 n1下标就越界了。我见过太多人在考试里因为这个越界产生诡异结果排查半天才发现是数组开小了。3.2 二维差分矩形批量更新二维差分是二维前缀和的逆运算用于解决“矩形区域统一加 v”的问题。假设要对左上角 (x1, y1)、右下角 (x2, y2) 的区域整体加 v在二维差分数组 diff 上做如下四次更新diff[x1][y1] v; diff[x1][y2 1] - v; diff[x2 1][y1] - v; diff[x2 1][y2 1] v;做完所有更新后对 diff 做一次二维前缀和得到的就是每个格子最终的增量。这个公式跟前缀和查询公式长得像一对镜像核心还是容斥。你可以这样理解在 (x1, y1) 处放一个正标记v 会向右下扩散在 (x1, y21) 和 (x21, y1) 处放两个负标记限制扩散范围但因为两个负标记的影响在 (x21, y21) 处重叠导致这里被减了两次所以还要再补一个正标记加回来。二维差分模板int diff[N][N]; for (int i 0; i m; i) { int x1, y1, x2, y2; long long v; cin x1 y1 x2 y2 v; diff[x1][y1] v; diff[x1][y2 1] - v; diff[x2 1][y1] - v; diff[x2 1][y2 1] v; } for (int i 1; i n; i) for (int j 1; j n; j) { diff[i][j] diff[i - 1][j] diff[i][j - 1] - diff[i - 1][j - 1]; a[i][j] diff[i][j]; }二维差分在蓝桥杯里经常和“地毯铺设”“海报送达”“棋盘染色”这类背景结合本质都是矩阵区域更新后求最终矩阵。熟练掌握这套模板后此类题基本就是送分题。3.3 差分经典模型区间覆盖计数区间覆盖计数是我个人认为差分最有实用价值的模型。题目通常长这样给定若干个区间 [l, r]问每个位置点被多少个区间覆盖或者求被覆盖次数最多的位置的值。思路是用差分把区间端点信息记录下来每个区间进来时在 l 处 1在 r1 处 -1所有区间处理完后求一次前缀和d[i] 就是位置 i 被覆盖的次数。这个模型在蓝桥杯真题中出现频率很高而且往往还会加点变化比如区间覆盖的不是连续整数点而是线段需要求被覆盖的总长度或者位置很多但区间数量不大需要用离散化配合。我曾经带学生刷过一组题从“统计每个点被覆盖次数”到“大坐标下统计覆盖总长度”其实就是在这个模型上逐步加难度。只要把区间端点记录和差分前缀和还原的底层逻辑搞懂这些变形很快就能想通。3.4 差分不能解决的场景在线更新查询需明确一个边界普通差分只支持“全部更新结束后再查询”。如果题目要求每次更新后立即回答查询比如“每次把 [l, r] 区间加 v然后立即问 a[p] 的值”普通差分就完全失效。这种在线场景必须使用树状数组或线段树。前者用差分思想维护单点查询后者直接维护区间信息。蓝桥杯省赛中大多数区间更新题是离线形式差分足够应付但到了国赛在线更新的题目也会出现建议有能力的同学在掌握差分后继续学树状数组因为树状数组本质上就是对差分数组的前缀和做了动态维护学习成本并不高。4. 离散化把大坐标系压缩成小数组4.1 离散化到底解决了什么问题离散化解决的核心问题是空间。假设你要在 1 到 1e9 的坐标轴上做区间覆盖统计如果按坐标开数组需要开 1e9 个位置这在竞赛环境下完全不现实。但实际给出的区间数量可能只有 1e5 个涉及的坐标点最多 2e5 个每个区间两个端点。对这些坐标点重新编号为 1、2、3……数组大小只需要 2e5 级别就能容纳所有操作。这就像把一张巨大的地图里真正有用的地标全部挑出来给它们按顺序编号原本相隔千万里的坐标一下就变成了挨着的 1、2、3。你不需要关心地图上没被标记的空地因为所有区间的覆盖操作只会作用在地标上和地标之间的连续空地上而空地只需在最后统计长度时补算回来即可。离散化的标准步骤收集所有参与计算的坐标值放进一个数组 all。对 all 排序然后用 unique 去重。对每个原始坐标 x用 lower_bound 在 all 中找到它的位置返回下标作为新坐标。在新坐标数组上做差分、前缀和或树状数组统计。C 模板vectorint all; // 把所有坐标插入 all sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int get(int x) { return lower_bound(all.begin(), all.end(), x) - all.begin() 1; // 返回 1-based 下标 }Python 模板all_vals sorted(set(all_vals)) def get(x): return bisect_left(all_vals, x) 14.2 离散化结合查值用哈希代替二分如果你用 Java可以使用 TreeMap 或 HashMap 直接完成映射省去手写二分的繁琐。HashMap 的时间复杂度是 O(1)写起来更直观但常数较大数据量在 2e5 级别时没问题到 1e6 级别需要谨慎。C 里也有 unordered_map 可以替代但竞赛环境下 lower_bound 的二分写法反而更稳定因为 unordered_map 在极端数据下可能会因为哈希冲突退化。我的习惯是默认用排序加二分什么时候都不容易出错。不过映射之后有两类问题要特别注意。第一lower_bound 查不到目标时会返回 end()这表示原始的坐标 x 没有被收集进 all通常是收集阶段漏了某个关键端点导致的。第二映射后的下标从 1 开始还是从 0 开始会直接影响差分数组的边界建议统一用 1-based和前缀和那套保持同步。4.3 区间离散化的经典坑r 还是 r1这是离散化区间覆盖里最容易翻车的点必须单独拎出来讲。假设有两个区间 [1, 3] 和 [5, 7]你只收集了 l 和 r也就是 collect 了 1、3、5、7。离散化后映射成 1、2、3、4。如果在映射后的下标上直接做差分用 get(1)1、get(3)2、get(5)3、get(7)4更新 [1,3] 对应 d[1]1、d[3?]-?这里就出问题了区间 [1,3] 和 [5,7] 之间的空隙 3 到 5 被错误地合并成一个连续块导致统计覆盖次数时把空隙也算成了被覆盖。正确做法是把区间一律视作左闭右开 [l, r1)收集坐标时同时加入 l 和 r1。这样 [1,3] 变为 [1,4)[5,7] 变为 [5,8)离散化后的点列是 1、4、5、8通过差分还原就能准确区分“3 到 5 之间没有覆盖”。如果题目要求统计覆盖长度还要对相邻离散坐标之间的真实距离加权。比如离散化后坐标 1 和 4 之间的宽度是 3那么这整段的覆盖次数如果要折算成覆盖长度就必须乘上这个间距。这个权重处理经常配合差分一起出现是蓝桥杯国赛难度的常见考法。4.4 用离散化做题的完整例子给你一个坐标轴初始所有位置覆盖次数为 0。执行 3 次操作区间 [2, 6] 覆盖次数 1区间 [4, 8] 覆盖次数 1区间 [10, 12] 覆盖次数 1最后求覆盖次数超过 1 的总长度。坐标范围到 1e9所以必须离散化。按照前面的规则把每个区间变成左闭右开 [l, r1)收集所有端点2、7、4、9、10、13排序去重后为 2、4、7、9、10、13映射为 1 到 6。在映射下标上做差分区间 [2,7)d[1]1d[2]-1区间 [4,9)d[2]1d[3]-1区间 [10,13)d[5]1d[6]-1对差分做前缀和得到每段的覆盖次数。真正要统计长度时需要把相邻映射点之间的原坐标距离计算出来2 到 4 距离 24 到 7 距离 37 到 9 距离 29 到 10 距离 110 到 13 距离 3。只有距离大于 0 的连续段才有实际长度。最终答案就是覆盖次数大于 1 的各段长度相加4 到 7 距离 310 到 13 距离 3合计 5。这个例子完整展示了“离散化 差分 前缀和 距离加权”的处理流程自己在草稿纸上跑一遍比看十遍代码都有用。5. 实战复盘三道蓝桥杯风格题目串起全程5.1 静态区间和查询题目背景常见为一个长度为 n 的整数数组m 次询问每次给 l 和 r求 [l, r] 的和。n、m 都在 1e5 级别。这题直接做就是 TLE用一维前缀和预处理 O(n)每次查询 O(1)。我做这题时会先用暴力写一遍确认题意和数据范围然后立刻切到前缀和模板。真正容易丢分的是输出格式和数据类型。如果需要输出多行结果C 记得用 \n 而不是 endl否则大量换行刷新会明显变慢Java 建议用 StringBuilder 拼接Python 用 \n.join 一次性输出。这种小细节在蓝桥杯的时间限制下往往就是 0 分和满分的区别。5.2 多次区间更新最后查询题目背景长度为 n 的数组初始为 0执行 m 次“把 [l, r] 每个元素加上 v”操作最后输出完整数组。n、m 在 1e5 级别。暴力 O(n*m) 不可行用差分就能轻松解决。实现时注意差分数组开 n2每次更新 d[l] v、d[r1] - v最后做前缀和还原。这题的拓展版本会要求“输出最大值”或“输出某个位置的值”基本思路一致只是还原后要遍历一次统计答案。还有一类变种叫“区间异或更新”“区间赋值更新”虽然操作的运算符不同但差分的核心思想不变在端点处打标记最后统一生效。理解这点你就能应对很多表面包装不同的题目。5.3 大坐标区间覆盖统计题目背景数轴上有若干个区间坐标范围极大求被覆盖次数最多的位置被覆盖了多少次。这类题必须离散化加差分。收集所有区间端点和端点加一排序去重映射在映射后的下标上做差分最后前缀和还原。还原后遍历每个离散段用段长乘以覆盖次数就能得到加权统计结果。这个过程中最容易出现的两个问题一是漏收集 r1导致相邻区间被错误连接二是还原后忘了把长度权重乘回去导致覆盖总长度算错。我在训练时要求学生必须用“左右端点 左端点减一”或者“左端点 右端点加一”统一成左闭右开区间从源头规避第一类问题。至于第二类问题可以通过一个包含重叠区间的自定义样例来验证。我常用的样例是 [1,5] 和 [3,10]覆盖 1 次长度为 2覆盖 2 次长度为 3总长度为 8如果程序输出不是这个数说明长度加权处理有问题。6. 刷题路线与高频 Bug 检查清单6.1 从模板到真题的刷题顺序很多同学一上来就刷蓝桥杯真题遇到不会的题就看题解看完觉得懂了隔几天再写还是不会。我建议按照“模板 → 变形 → 真题 → 综合”的顺序来。第一阶段把一维前缀和、二维前缀和、一维差分、二维差分、离散化五个模板各写三遍争取五分钟内无错写出。第二阶段做区间覆盖计数、子矩阵求和、坐标压缩后的差分题熟悉变形套路。第三阶段刷蓝桥杯历年真题中的区间类题目建议按年份从旧到新把同一类的题放一起刷方便横向对比出题风格。第四阶段尝试做国赛题和 NOIP 提高组真题中涉及离散化的综合题因为国赛的区间题很少单独考一个算法大多要配合树状数组、贪心、二分答案一起用。需要特别提醒的是“蚂蚁感冒”这类思维题。有一年蓝桥杯省赛出了蚂蚁感冒的变种很多人第一反应是用模拟模拟蚂蚁运动结果陷入状态循环。它实际上是一个区间思考题本质是讨论在数轴上相遇后方向改不改变的问题跟差分前缀和没有直接关联。这种题提醒我们看到区间相关背景不要条件反射套算法先静下来把模型抽象出来判断到底属于哪个知识点。区间背景的题可能是差分可能是扫描线也可能只是朴素分类讨论。6.2 我踩过的坑高频 Bug 清单把这些年带学生和自己参赛时经常踩的坑整理成一个清单每次写完代码都对照检查一遍能省下大量调试时间数组开小了差分需要访问 r1数组必须开 n2 或更大二维同理要预留出 x21、y21 的位置。前缀和数组忘记从 1 开始下标从 0 开始会引发 s[l-1] 为负数下标的问题。求和结果爆 int前缀和、差分还原后的累加结果都可能超过 int统一用 long long。把答案数据类型跟输入搞混输入可能是 int 范围但中间结果不是输出前强制转 long long。二维前缀和或二维差分公式写串在纸上先画一遍容斥关系确认加减号的个数。离散化后的坐标映射出错检查 lower_bound 返回位置是否合法尤其是端点没有提前收集时容易查不到。区间离散化漏掉 r1这是我最常见的错误也是最隐蔽的。还原时漏掉长度加权统计总长度、总面积类问题必须考虑离散坐标之间的距离或面积。6.3 比赛现场的时间分配建议蓝桥杯省赛的时间很紧张遇到区间类题目我一般在读题后 30 秒内判断它属于哪种模型然后直接套模板。判断方法其实很机械题目问“区间和”、“子矩阵和”优先前缀和题目说“多次区间更新”、“最后输出”优先差分数字范围大到 1e9但操作数只有 1e5优先离散化。这三个判断在我脑子里是条件反射级别的因为模板题在比赛里就是送分题送分题绝不能因为犹豫而浪费宝贵时间。如果你发现自己写代码经常在边界处卡住我还有一个很蠢但很有效的办法把每个模板的边界样例默写出来。比如一维前缀和写一个 l1、rn 的查询二维前缀和查一个单行单列的子矩阵差分写一个 rn 的操作离散化写一个区间端点相邻或重叠的样例。在纸上验证一遍花不了三分钟但能拦住八成边界 bug。我自己的备赛包里一直存着这些小样例比赛时每次写完模板题都会快速验证一遍这个习惯让我少丢了很多冤枉分。最后分享一点个人经验。我带学生准备蓝桥杯时要求他们把这五个模板的代码手写至少十遍不是背代码而是背思路。等你闭着眼都能把下标和边界写对比赛时遇到区间题就有一种“这题我见过”的踏实感。三个算法加一个离散化说穿了就是一把组合武器武器越趁手上了考场心里越有底。后续如果你还想继续深入可以试着把这套东西和树状数组、扫描线、二分答案组合起来用那又是一片新的天地。
