前缀和算法差分算法（3）——例题详解

1.3 前缀和与差分例题详解

1.3.0 习题总览

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

学习说明：本节仅对前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