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

1.3 前缀和与差分例题详解

1.3.0 习题总览

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

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

1.3.1 例题一：P2367 语文成绩

题意简述

给定长度为

n

n

n 的初始数组

a

a

a，进行

p

p

p 次区间修改操作：每次将区间

[

x

,

y

]

[x,y]

[x,y] 内的所有元素增加数值

z

z

z。所有操作完成后，输出数组中的最小值。

算法分析

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

若采用暴力枚举区间修改，时间复杂度为

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

v

v，只需执行

d

[

l

]

+

=

v

、

d

[

r

+

1

]

−

=

v

d[l]+=v、d[r+1]-=v

d[l]+=v、d[r+1]−=v。本题输入为1下标格式，代码中需转换为0下标适配数组。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 10;
int a[maxn], d[maxn];

// 快速循环宏
#define _for(i, n) for (int i = 0; i < n; i++)
#define _rep(i, a, b) for (int i = a; i < b; i++)
#define endl '\\n'

int main()
{
// 关闭同步，加速输入输出
ios::sync_with_stdio(0);
cin.tie(0);

int n, p;
cin >> n >> p;
// 读入初始数组
_for(i, n) cin >> a[i];

// 构建一维差分数组
d[0] = a[0];
_rep(i, 1, n) d[i] = a[i] – a[i – 1];

// 执行p次区间修改
_for(i, p)
{
int l, r, v;
cin >> l >> r >> v;
l—; r—; // 1下标转0下标
d[l] += v;
d[r + 1] -= v;
}

// 前缀和还原原数组
a[0] = d[0];
_rep(i, 1, n) a[i] = d[i] += d[i – 1];

// 遍历求数组最小值
int minn = INT_MAX;
_for(i, n) minn = min(minn, a[i]);

cout << minn << endl;
return 0;
}

解题总结

一维差分的核心适用场景：大量区间整体加减、最后统一查询数组数值。只要题目出现多次区间修改、单次最终查询的特征，优先考虑差分算法。

1.3.2 例题二：P2280 激光炸弹

题意简述

给定

n

n

n 个带权坐标点

(

x

,

y

,

v

)

(x,y,v)

(x,y,v)，表示地图坐标

(

x

,

y

)

(x,y)

(x,y) 处存在价值为

v

v

v 的目标。炸弹可摧毁一个边长为

m

m

m 的正方形区域内的所有目标，求单次爆炸能摧毁的最大总价值。其中

0

≤

x

,

y

≤

5

×

10

3

0 \\le x,y \\le 5\\times10^3

0≤x,y≤5×103，

1

≤

n

≤

10

4

1 \\le n \\le 10^4

1≤n≤104。

算法分析

本题是二维前缀和经典模板题，核心问题可转化为：在固定尺寸的二维网格中，求解边长为

m

m

m 的子矩阵的最大权值和。

解题思路：首先构建二维权值地图，将所有坐标点的权值累加至对应位置；再预处理二维前缀和数组，利用前缀和公式

O

(

1

)

O(1)

O(1) 求解任意子矩阵和；最后遍历所有合法的

m

×

m

m\\times m

m×m 正方形，更新最大值答案。

关键细节：题目坐标从0开始，为避免前缀和计算时出现下标越界，代码中将所有坐标统一+1转为1下标，适配二维前缀和常规写法。整体时间复杂度

O

(

N

2

)

O(N^2)

O(N2)（

N

=

5

×

10

3

N=5\\times10^3

N=5×103），完全符合时间限制。

AC代码

#include <bits/stdc++.h>
using namespace std;

#define _for(i, n) for (int i = 0; i < n; i++)
#define _rep(i, a, b) for (int i = a; i < b; i++)
#define endl '\\n'

const int maxx = 5e3 + 10;
int mp[maxx][maxx]; // 权值地图
int pre[maxx][maxx]; // 二维前缀和数组

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

int n, m;
cin >> n >> m;

// 初始化地图权值
_for(i, n)
{
int x, y, v;
cin >> x >> y >> v;
x++; y++; // 0下标转1下标
mp[x][y] += v;
}

// 预处理二维前缀和
_rep(i, 1, maxx)
_rep(j, 1, maxx)
pre[i][j] = mp[i][j] + pre[i–1][j] + pre[i][j–1] – pre[i–1][j–1];

int maxv = INT_MIN;
// 遍历所有合法m*m正方形
_rep(i, 1, maxx – m)
{
_rep(j, 1, maxx – m)
{
int x2 = i + m – 1;
int y2 = j + m – 1;
// 子矩阵和计算公式
int sum = pre[x2][y2] – pre[i–1][y2] – pre[x2][j–1] + pre[i–1][j–1];
maxv = max(maxv, sum);
}
}

cout << maxv << endl;
return 0;
}

解题总结

二维前缀和核心作用：预处理后快速查询任意子矩阵权值和，是解决二维区间最值、区间求和问题的基础算法，固定尺寸子矩阵遍历是高频考法。

1.3.3 例题三：P13787 地毯

题意简述

在

n

×

n

n\\times n

n×n 的空地板上铺设

m

m

m 块矩形地毯，给定每块地毯的左上角和右下角坐标。设

F

i

,

j

F_{i,j}

Fi,j​ 为坐标

(

i

,

j

)

(i,j)

(i,j) 处覆盖的地毯数量，求所有位置满足

∑

i

=

1

n

∑

j

=

1

n

(

i

+

j

)

⊕

F

i

,

j

\\sum_{i=1}^n\\sum_{j=1}^n (i+j)\\oplus F_{i,j}

∑i=1n​∑j=1n​(i+j)⊕Fi,j​ 的总和（

⊕

\\oplus

⊕ 为异或运算）。

算法分析

本题核心考点为二维差分。题目需求为多次矩形区间整体+1，最后统计每个点的数值，属于二维差分标准场景。

若暴力遍历每个地毯的矩形区间修改，时间复杂度为

O

(

m

n

2

)

O(mn^2)

O(mn2)，面对题目大数据范围会严重超时；而二维差分可将单次矩形修改优化为

O

(

1

)

O(1)

O(1)，最后通过两次前缀和还原整个二维数组，整体复杂度

O

(

n

2

+

m

)

O(n^2+m)

O(n2+m)。

二维差分核心规则：对矩形

(

x

1

,

y

1

)

∼

(

x

2

,

y

2

)

(x1,y1)\\sim(x2,y2)

(x1,y1)∼(x2,y2) 整体+1，执行：

a

[

x

1

]

[

y

1

]

+

+

、

a

[

x

2

+

1

]

[

y

1

]

−

−

、

a

[

x

1

]

[

y

2

+

1

]

−

−

、

a

[

x

2

+

1

]

[

y

2

+

1

]

+

+

a[x1][y1]++、a[x2+1][y1]–、a[x1][y2+1]–、a[x2+1][y2+1]++

a[x1][y1]++、a[x2+1][y1]−−、a[x1][y2+1]−−、a[x2+1][y2+1]++。

最后遍历还原后的数组，按题意计算异或累加和即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define _for(i, n) for (int i = 1; i <= n; i++)
#define endl '\\n'
const int maxn = 5e3 + 10;
int a[maxn][maxn]; // 二维差分数组

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

int n, m;
cin >> n >> m;
// 二维差分处理所有矩形覆盖操作
while (m—)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
a[x1][y1]++;
a[x2 + 1][y1]—;
a[x1][y2 + 1]—;
a[x2 + 1][y2 + 1]++;
}

// 第一次前缀和：还原行维度
_for(i, n)
_for(j, n)
a[i][j] += a[i – 1][j];

// 第二次前缀和：还原列维度，得到真实覆盖次数
_for(i, n)
_for(j, n)
a[i][j] += a[i][j – 1];

// 按题意计算最终累加和
ll sum = 0;
_for(i, n)
_for(j, n)
sum += (i + j) ^ a[i][j];

cout << sum << endl;
return 0;
}

解题总结

二维差分专门解决大规模二维矩形区间批量修改问题，核心是通过四次单点修改替代区间遍历，最后通过两遍前缀和还原数组，是二维区间操作的最优解之一。

1.3.4 例题四：P1115 最大子段和

题意简述

给定长度为

n

n

n 的整数序列，选取一段连续非空子序列，使得该子序列的和最大，输出这个最大和。

算法分析

本题是经典贪心+前缀和综合题，此处采用前缀和优化的思路求解（适配本章知识点体系）。

基础结论：区间

[

l

,

r

]

[l,r]

[l,r] 的和可表示为

s

u

m

(

l

,

r

)

=

p

r

e

[

r

]

−

p

r

e

[

l

−

1

]

sum(l,r)=pre[r]-pre[l-1]

sum(l,r)=pre[r]−pre[l−1]，其中

p

r

e

[

r

]

pre[r]

pre[r] 为前

r

r

r 项前缀和。想要让区间和最大，对于固定的右端点

r

r

r，只需让

p

r

e

[

l

−

1

]

pre[l-1]

pre[l−1] 尽可能小（

l

≤

r

l\\le r

l≤r）。

优化思路：遍历数组过程中，实时维护当前最小前缀和。每遍历到一个位置，计算「当前前缀和-最小前缀和」，更新全局最大值，全程仅需一次遍历，时间复杂度

O

(

n

)

O(n)

O(n)，空间复杂度

O

(

1

)

O(1)

O(1)，无需存储完整前缀和数组。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
int n;
cin >> n;
ll sum = 0; // 实时记录当前前缀和
ll min_s = 0; // 记录遍历到当前位置的最小前缀和
ll ans = INT_MIN;

while (n—)
{
int x;
cin >> x;
sum += x;
// 更新最大子段和
ans = max(ans, sum – min_s);
// 更新最小前缀和
min_s = min(min_s, sum);
}

cout << ans << endl;
return 0;
}

解题总结

前缀和不仅能用于区间求和，还能结合最值维护，将区间最值问题转化为单点遍历最值差值问题，大幅优化时间复杂度，是前缀和进阶应用的核心思想。

1.3.5 本节小结

本节通过4道核心例题，完整讲解了一维前缀和、一维差分、二维前缀和、二维差分四大核心算法的模板用法与基础应用。四类算法的代码逻辑简单、固定，但解题难点在于从复杂题意中识别对应算法场景。

课后学习建议：优先完成16道习题中的12道基础及应用题，熟练掌握算法模板与场景匹配；最后4道高难度题目可作为拔高训练，突破思维局限，彻底吃透前缀和与差分的全套解题体系。