蓝桥杯算法精讲：前缀和与差分算法的应用与实战

云泽808

发布于 2025-12-30 18:34:44

2130

前言

大家好啊，我是云泽Q，欢迎阅读我的文章，一名热爱计算机技术的在校大学生，喜欢在课余时间做一些计算机技术的总结性文章，希望我的文章能为你解答困惑~

一、前缀和

前缀和与差分的核心思想是预处理，可以在暴力枚举的过程中，快速给出查询的结果，从而优化时间复杂度。由于前缀和和差分在预处理的时候一般需要定义额外的数组来存储预处理的结果，所以前缀和也是经典的用空间替换时间的做法

1.1 一维前缀和

【模板】前缀和

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
LL a[N], f[N];
int n, m;

int main()
{
	cin >> n >> m;
	//向初始数组存入数据 
	for(int i = 1; i <= n; i++) cin >> a[i];
	//创建前缀和数组 
	for(int i = 1; i <= n; i++) f[i] = f[i - 1] + a[i];
	//处理m次询问 
	while(m--)
	{
		int l, r; cin >> l >> r;
		cout << f[r] - f[l - 1] << endl;
	}
	return 0;
}

1.2 最大子段和

最大子段和

解法这道题解法有多种，这里介绍前缀和解法。考虑以 i 位置的元素 a[i] 为结尾的最大子段和：

在求区间和时，相当于是用 f[i] 减去 i 位置前面的某一个 f[x]
如果想要最大子段和，也就是最大区间和，那么用 f[i] 减掉一个前驱最小值即可

因此可以创建 a 数组的 前缀和数组，然后在遍历前缀和数组的过程中，一边更新前驱最小值，一边更新当前位置为结尾的最大子段和

#include <iostream>
using namespace std;

typedef long long LL;  // 避免溢出 
const int N = 2e5 + 10;  // 数组大小
int n;
LL f[N];  // f[i]：前i个数的前缀和

int main()
{
    cin >> n;
    // 第一步：计算前缀和数组f
    for(int i = 1; i <= n; i++)
    {
        LL x; cin >> x;  // 读入序列的第i个数a[i]
        f[i] = f[i - 1] + x;  // 前缀和递推：f[i] = 前i-1项和 + 当前项
    }

    LL ret = -1e20;  // 存储最终答案，初始化为极小值（避免全负数的情况）
    LL prevmin = 0;  // 维护前k项前缀和的最小值（初始为f[0]=0）

    // 第二步：遍历每个元素，计算最大子段和
    for(int i = 1; i <= n; i++)
    {
        // 以i结尾的最大子段和 = f[i] - 前i-1项中最小的f[k]
        ret = max(ret, f[i] - prevmin);
        // 更新前缀最小值：把当前f[i]加入候选，取更小值
        prevmin = min(prevmin, f[i]);
    }

    cout << ret << endl;
    return 0;
}

样例模拟（以题目样例为例） 样例输入：

7
2 -4 3 -1 2 -4 3

步骤 1：计算前缀和数组 f 规定 f[0] = 0，则：

f[1] = f[0] + 2 = 2
f[2] = f[1] + (-4) = -2
f[3] = f[2] + 3 = 1
f[4] = f[3] + (-1) = 0
f[5] = f[4] + 2 = 2
f[6] = f[5] + (-4) = -2
f[7] = f[6] + 3 = 1 步骤 2：遍历计算最大子段和 初始化 ret = -1e20，prevmin = 0（即 f[0]）：

补充几点

数据类型必须用 long long：序列中每个数的范围是 -1e4 ~ 1e4，n=2e5 时，最大可能和为 2e5 × 1e4 = 2e9，超过了 int 的范围（int 最大为 231-1=2147483647≈2e9，刚好卡边界，实际会溢出），因此必须用 long long 存储前缀和与结果。

下面是最大和为2e9的场景整个序列的所有元素都是最大值 1e4，且我们选择的子段是 “整个序列”（因为全是正数，越长和越大）。

此时子段和 = 元素个数 × 单个元素最大值，代入最大值计算：

元素个数取最大：2×10⁵（2e5）；
单个元素取最大：1×10⁴（1e4）；
相乘得：2×10⁵ × 1×10⁴ = 2×10⁹（2e9，也就是 2000000000）。

ret用于统计所有情况下的最大值，初始情况下初始化为无穷小，切记不能初始化为0，因为数组中的有些数是小于0的，若数组中的所有数都小于0，也就是说最小子段和是个负数，取max最终结果就会是0
在计算数组中第一个元素的最小子段和时，其前面是没有前缀和的，默认这个前缀和为0

1.3 二维前缀和

【模板】二维前缀和

解法二维前缀和模板题，直接套用公式创建前缀和矩阵，然后利用前缀和矩阵的性质处理q次访问

创建前缀和矩阵：f[i][j] = f[i - 1][j] + f[i][j - 1] -f[i - 1][j - 1] + a[i][j]

查询以（x1, y1）为左上角，（x2，y2）为右下角的子矩阵的和

#include<iostream>
using namespace std;

const int N = 1010;
typedef long long LL;
int n, m, q;
LL f[N][N];

int main()
{
	cin >> n >> m >> q;
	//预处理前缀和矩阵 
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			LL x; cin >> x;
			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + x;
		}
	}
	//处理q次查询
	while(q--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << endl;
	 } 
	return 0;
}

1.4 激光炸弹

激光炸弹

#include<iostream>
using namespace std;

// 数组最大尺寸
const int N = 5010;
// n：初始表示目标点的数量，后续复用为前缀和矩阵的最大有效下标；m：爆破正方形的边长
int n, m;
int a[N][N];// 存储每个坐标点的目标总价值（同一坐标可能有多个目标，价值累加）
int f[N][N];// 二维前缀和矩阵，用于快速计算任意矩形区域的总价值 

int main()
{
    cin >> n >> m;
    
    // 循环读取每个目标点的信息
    while(n--)
    {
        int x, y, v; // x/y：目标原始坐标，v：该目标的价值
        cin >> x >> y >> v;
        // 坐标转为1-based（避免前缀和计算时i-1/j-1越界）
        x++; y++;
        a[x][y] += v; // 同一坐标多个目标，价值累加
    }
    
    // 前缀和矩阵的有效范围：原始坐标0~5000 → 1-based后1~5001
    n = 5001;
    
    // 构建二维前缀和矩阵
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
        }
    }
    
    int ret = 0; // 记录爆破正方形能覆盖的最大目标总价值
    m = min(n, m); // 防止正方形边长超过矩阵有效范围
    
    // 暴力枚举所有边长为m的正方形（枚举右下角坐标(x2,y2)）
    for(int x2 = m; x2 <= n; x2++)
    {
        for(int y2 = m; y2 <= n; y2++)
        {
            // 由右下角坐标推导左上角坐标
            int x1 = x2 - m + 1, y1 = y2 - m + 1;
            ret = max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]);
        }
    }
    
    // 输出最大可爆破的目标总价值
    cout << ret << endl;
    return 0;
}

这里说一下：为什么知道正方形的右下角下标若等于（x2，y2），其左上角下标为（x2 - m + 1，y2 - m + 1）

二、差分

前缀和与差分的核心思想是预处理，可以在暴力枚举的过程中，快速给出查询的结果，从而优化时间复杂度，是经典的空间替时间的做法。且前缀和与差分是一对互逆的运算

2.1 一维差分

【模板】差分

该题目同一种思路有两种写法：

第一种

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
int n, m;
LL a[N], f[N];

int main()
{
	cin >> n >> m;
	//利用差分性质创建差分数组
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		f[i] = a[i] - a[i - 1];
	}
	//处理 m 次操作
	while(m--)
	{
		int l, r; LL k; cin >> l >> r >> k;
		f[l] += k; f[r + 1] -= k;
	}
	//还原出原始数组 
	for(int i = 1; i <= n; i++)
	{
		a[i] = a[i - 1] + f[i];
		cout << a[i] << " ";
	 } 
	return 0;
}

第二种

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
int n, m;
LL f[N];

int main()
{
	cin >> n >> m;
	//利用差分的性质，创建差分数组 
	for(int i = 1; i <= n; i++)
	{
		LL x; cin >> x;
		f[i] += x;
		f[i + 1] -= x;
	}
	//处理 m 次操作 
	while(m--)
	{
		int l, r; LL k; cin >> l >> r >> k;
		f[l] += k; f[r + 1] -= k; 
	}
	//还原出原数组
	for(int i = 1; i <= n; i++)
	{
		f[i] = f[i - 1] + f[i];
		cout << f[i] << " ";
	 } 
	return 0;
}

第二种写法的核心巧思：把 “初始化原始数组的每个元素”，等价成 “对长度为 1 的区间 [i,i] 加初始值”，从而不用额外存原始数组。

样例落地：n=3，原始数组 a = [2,5,7]

步骤 1：差分数组的创建（第二种写法的核心逻辑）第二种写法代码中，差分数组 f 初始全为 0（f[0]=f[1]=f[2]=f[3]=f[4]=0，下标到 n+1 是为了避免越界）。循环读入每个初始值，执行 “区间 [i,i] 加 x” 的差分操作：

最终得到的差分数组 f = [0,2,3,2,-7]（下标 0~4）。

步骤 2：还原原始数组（前缀和操作） 对差分数组 f 求前缀和，每一步的结果就是原始数组的对应位置：

可以看到，前缀和的结果完全还原了原始数组 [2,5,7]。这种写法的核心优势是无额外数组开销，逻辑更紧凑，是差分写法的 “优化版”。

2.2 海底高铁

海底高铁

解法先考虑如何让花费最小，想要求最小花费，需要知道每一段高铁被乘坐了多少次，记作k，那么最小花费就是买票的花费与买卡的花费两者之间的最小值

买票花费：a × k
买卡花费，乘车花费 + 工本费 c + bk
那么最小花费就是minconst = min（ak，c + bk）

接下来考虑如何求出每一段高铁被乘坐了多少次。根据访问城市的序列 l 到 r 可知，对于任意一次访问，我们会乘坐 [l, r - 1]之间所有的高铁，比如 l = 3，r = 6，那么[3, 5]之间所有的高铁都会被乘坐一次，相当于每个数都加上1，注意 6 位置不会乘坐到，那么我们就可以利用差分数组

创建一个全为 0 的差分数组 f
遍历访问序列，对于每一次访问：f[l]++，f[r]- -
然后对差分数据做一次前缀和，就能得到每个高铁的乘坐次数

#include<iostream>
using namespace std;

const int N = 1e5 + 10;  // 数据范围：城市数/铁路段数上限
typedef long long LL;     // 防止整数溢出，统一用LL处理大数

int n, m;                // n：城市总数，m：行程经过的城市数
LL f[N];                 // 差分数组：统计每个铁路段被经过的次数

int main()
{
    cin >> n >> m;
    int x; cin >> x;     // 读入行程的第一个城市
    // 处理m个城市的行程（共m-1段行程），用差分数组标记次数
    for(int i = 2; i <= m; i++)
    {
        int y; cin >> y; // 读入当前行程的终点城市
        // 差分数组标记：x到y之间的铁路段次数+1
        if(x > y)
        {
            f[y]++;
            f[x]--;
        }else{
            f[x]++;
            f[y]--;
        }
        x = y; // 更新起点为当前终点，处理下一段行程
    }

    // 差分数组求前缀和，还原每个铁路段的实际经过次数
    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i] + f[i - 1];
    }

    LL ret = 0; // 总费用
    // 遍历所有n-1个铁路段，计算最小费用
    for(int i = 1; i < n; i++)
    {
        LL a, b, c; cin >> a >> b >> c; // a：纸质票单价，b：IC卡单价，c：IC卡工本费
        // 累加：纸质票总费用(a*次数) 和 IC卡总费用(工本费+单价*次数) 的最小值
        ret += min(a * f[i], c + b * f[i]);
    }

    cout << ret << endl; // 输出最终总费用
    return 0;
}

注意1：城市访问的序列有可能l > r，此时应该交换一下顺序

注意2：某一段铁路钱的数据范围是105，经过的城市和要去的城市的范围也是105，随便加加减减就有可能超过int的取值范围，这里typedef一下，用LL存差分数组

注意3：再说一下第二个for循环和第三个for循环范围的原因 第三个for循环：i从1到n-1

for(int i = 1; i < n; i++)

背景：铁路段的数量是n-1个（连接1-2、2-3…n-1-n）。
范围原因：循环i从1到n-1，刚好覆盖所有铁路段。
作用：对每个铁路段，输入其A_i, B_i, C_i，计算 “买纸质票” 和 “买 IC 卡” 的最小费用，累加到总费用中。

第二个for循环：i从1到n

for(int i = 1; i <= n; i++) f[i] += f[i - 1];

“铁路段个数是 1 到 n-1 ” 完全正确，最终我们只需要 f[1] 到 f[n-1] 的值（对应每个铁路段的经过次数）；代码里循环到 n ，只是差分数组计算前缀和的 “完整写法”，对结果没有任何影响。

为什么循环到n也没问题？ 我们先回顾差分数组的操作逻辑：比如行程是x→y（x<y），我们做f[x]加加、f[y]减减—— 这里的y可能等于n（比如从n-1到n），此时f[n]会被减 1。如果第二个循环只算到n-1：

for(int i = 1; i <= n-1; i++) f[i] += f[i-1];

f[1] 到 f[n-1] 的结果依然完全正确（因为 f[n] 的值根本用不到）。代码里循环到n，只是：

差分数组前缀和的 “通用写法”（不管下标到多少，都从 1 累加到最后一个下标）；
就算多算一步f[n] = f[n] + f[n-1]，也不影响后续逻辑（第三个循环只用到 f[1]~f[n-1] ）。

再最后补充一点大家都有可能犯错的点，博主写这道题的时候也犯了这个错误 因为只要最后结果，把最后结果的数据类型写为LL是不行的 为什么只改 ret 没用？ 我们先看数据范围（结合题目背景：n/m是1e5级别）：

int的取值范围约为 ±2×109（32 位系统）；
f[i]是差分数组还原后的次数，最大可能达到m（比如所有行程都经过某一段），即1e5级别；
如果a是int类型（比如a=1e5），那么a * f[i] = 1e5 × 1e5 = 1e10 —— 这个值远超int的上限，会触发整数溢出（变成负数 / 乱码）。

此时哪怕ret是LL，也晚了：因为a * f[i]在计算时已经溢出（int 范围内算错了），再把错误的结果赋值给ret，最终答案必然错误。仅管在VS2022中a、b、c是int，C++ 会触发「隐式类型转换」—— 把int临时转成LL再和f[i]计算，但也是一种不规范的写法，换个编译器可能就不行了

2.3 二维差分

【模板】二维差分

解法二维差分模板题，先根据差分矩阵的性质创建差分矩阵，然后根据差分矩阵的性质处理q次区间修改，最后利用前缀和还原出原始的矩阵。因此，重点就是差分矩阵的性质

可以类比一维差分数组的性质，推导出二维差分矩阵的性质

在差分数组中的某个位置标记：表示后续元素统一被修改
在差分数组中求前缀和；能够还原出原始数组

假设我们需要将原始矩阵a中，以（x1, y1）为左上角，（x2, y2）为右下角的子矩阵的每个元素都加上k：

由此可得差分矩阵的性质： f[x1][y1] += k f[x1][y2 + 1] -= k f[x2 + 1][y1] -= k f[x2 + 1][y2 + 1] += k;

#include<iostream>
using namespace std;

const int N = 1010;
typedef long long LL;
int n, m, q;
LL f[N][N];

// 二维差分核心操作：给子矩阵(x1,y1)-(x2,y2)的所有元素加k（仅做差分标记）
void insert(int x1, int y1, int x2, int y2, LL k)
{
    // 二维差分的区间更新标记（四个角的增减操作）
	f[x1][y1] += k; f[x1][y2 + 1] -= k;
	f[x2 + 1][y1] -= k; f[x2 + 1][y2 + 1] += k;
}

int main()
{
	cin >> n >> m >> q; // 读入矩阵行数、列数、操作次数
	
	// 初始化差分数组：将初始矩阵元素转为「单点加」的差分操作
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			LL x; cin >> x;
			// 初始元素x等价于对(i,j)-(i,j)的子矩阵加x
			insert(i, j, i, j, x);
		}
	}
	
	// 处理q次矩阵区间加操作
	while(q--)
	{
		int x1, y1, x2, y2; LL k; 
		cin >> x1 >> y1 >> x2 >> y2 >> k; // 读入区间与增量
		insert(x1, y1, x2, y2, k); // 对目标子矩阵做差分标记
	}
	
	// 二维前缀和：将差分数组还原为最终矩阵
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			// 二维前缀和递推公式（还原差分标记）
			f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];
			cout << f[i][j] << " "; // 输出当前元素
		}
		cout << endl;
	 } 
	return 0;
}

2.4 地毯

地毯

#include<iostream>
using namespace std;

const int N = 1010;
int n, m;
int f[N][N];

// 二维差分操作：给子矩阵(x1,y1)-(x2,y2)的所有格子覆盖数+1
void insert(int x1, int y1, int x2, int y2, int k)
{
	f[x1][y1] += k; f[x1][y2 + 1] -= k;
	f[x2 + 1][y1] -= k; f[x2 + 1][y2 + 1] += k;
}

int main()
{
	cin >> n >> m;
	// 处理每个地毯：将其覆盖的子矩阵转为差分标记（覆盖数+1）
	while(m--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		insert(x1, y1, x2, y2, 1);
	}
	// 二维前缀和：将差分数组还原为每个格子的实际覆盖数，并输出
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
			cout << f[i][j] << " ";
		}
		cout << endl;
	} 
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数组