前缀和算法差分算法（3）——例题详解-三亩地-编程学习日记

1.3 前缀和与差分例题详解

1.3.0 习题总览

本节围绕一维/二维前缀和、一维/二维差分核心知识点展开，精选20道洛谷经典题目，覆盖模板入门、基础练习、思维应用、综合进阶四大难度梯度。其中前4题为重点讲解例题，后16题为课后巩固习题，最后4道难题为选做提升内容，适合拔高思维。所有题目分类、考点、难度梳理如下：

序号	题号	题目名称	题型分类	难度定位	核心考点
1	P2367	语文成绩	一维差分	模板入门	一维差分、区间修改、单点查询
2	P2280	激光炸弹	二维前缀和	模板入门	二维前缀和、子矩阵最大求和
3	P13787	地毯	二维差分	模板入门	二维差分、矩形区间覆盖统计
4	P1115	最大子段和	一维前缀和	经典例题	前缀和求区间最值、线性优化
5	P3131	Subsequences Summing to Sevens S	一维前缀和	基础练习	前缀和+模运算、余数计数统计
6	P1719	最大矩形	一维前缀和	基础练习	矩阵压维、最大子矩阵求解
7	P2879	Tallest Cow S	一维差分	基础练习	一维差分，区间去重
8	P1314	聪明的质检员	一维前缀和	基础练习	前缀和求区间最值、二分答案
9	P5637	光骓者的荣耀	一维前缀和	基础练习	前缀和预处理区间代价
10	P4231	三步必杀	二阶差分	差分应用题	二阶差分应用
11	P3406	海底高铁	一维差分	差分应用题	差分统计区间经过次数、代价计算
12	P2082	区间覆盖	一维差分	差分应用题	差分求解区间总覆盖长度
13	P4552	Inc Sequence	一维差分	差分思维题	差分转化、区间操作转单点操作
14	P2004	领地选择	二维前缀和	二维练习	固定大小子矩阵最大值求解
15	P1627	中位数	前缀和 + 正负映射	前缀和进阶	一维前缀和综合运用
16	P1496	火烧赤壁	一维差分	综合进阶	离散化+差分、大范围区间统计
17	P10837	云音泛	一维前缀和	综合进阶	前缀和总和大题应用
18	P2679	子串	前缀和优化DP	综合进阶	前缀和优化动态规划、复杂度降维
19	P3943	星空	差分	综合难题	差分模拟区间翻转、思维转化
20	P1381	单词背诵	一维前缀和	综合进阶	滑动窗口+前缀和区间统计

学习说明：本节仅对前4道核心例题进行完整思路+代码详解；后16道习题配套独立题解，可自行练习巩固。其中最后4道难题综合性强、思维难度较高，建议学完基础内容后选做，用于拔高算法思维。

1.3.1 例题一：P2367 语文成绩

题意简述

给定长度为n nn的初始数组a aa，进行p pp次区间修改操作：每次将区间[ x , y ] [x,y][x,y]内的所有元素增加数值z zz。所有操作完成后，输出数组中的最小值。

算法分析

本题是一维差分的纯模板入门题，完美匹配差分算法的核心适用场景：多次区间加减、最终单点查询。

若采用暴力枚举区间修改，时间复杂度为O ( p n ) O(pn)O(pn)，在数据范围较大时会直接超时；而一维差分可以将单次区间修改的复杂度降为O ( 1 ) O(1)O(1)，整体复杂度仅为O ( n + p ) O(n+p)O(n+p)，效率极高。

核心思路：构建原数组的差分数组，利用差分性质完成区间修改，最后通过前缀和还原修改后的原数组，遍历求得最小值。

差分核心规则：对区间[ l , r ] [l,r][l,r]加v vv，只需执行d [ l ] + = v 、 d [ r + 1 ] − = v d[l]+=v、d[r+1]-=vd[l]+=v、d[r+1]−=v。本题输入为1下标格式，代码中需转换为0下标适配数组。

AC代码

#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e6+10;inta[maxn],d[maxn];// 快速循环宏#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'intmain(){// 关闭同步，加速输入输出ios::sync_with_stdio(0);cin.tie(0);intn,p;cin>>n>>p;// 读入初始数组_for(i,n)cin>>a[i];// 构建一维差分数组d[0]=a[0];_rep(i,1,n)d

日记详情