第一章 前缀和算法&差分算法

1. 前缀和算法&差分算法

本章将详细讲解前缀和与差分两种基础核心算法的核心定义、原理、使用场景及代码模板，两种算法是算法竞赛中高频出现的基础优化手段，适配区间操作类题型。本章所有代码案例已统一收录至代码仓库。代码仓库链接

1.1 算法核心定义与原理

1.1.1 前缀和算法

前缀和算法是区间求和专用的高效预处理优化算法，核心作用是将多次区间求和的时间复杂度大幅降低，完美解决大数据量区间求和超时问题。

在未优化的暴力解法中，若数组长度为 $x$，存在 $m$ 次区间查询，单次查询遍历区间长度为 $n$，整体时间复杂度为 $O(m\cdot n)$。当数据量达到 $10^5$ 级别时，暴力解法会直接超时。

而前缀和算法通过一次预处理、多次查询的思路，预处理时间复杂度为 $O(x)$，单次区间查询仅为 $O(1)$，海量查询场景下效率碾压暴力解法，是算法竞赛区间求和题型的必备技巧。

算法核心简述

定义原数组为 $a$（本文统一采用0下标存储），新建前缀和数组 $pre$。其中 $pre[i]$ 表示：原数组 $a$ 中前 $i+1$ 个元素的总和，即 $a[0]$ 到 $a[i]$ 的累加和。

前缀和数组递推规律如下：

$$\begin{gathered} pre[0]=a[0] \\ pre[1]=a[0]+a[1] \\ pre[2]=a[0]+a[1]+a[2] \\ \cdots \\ pre[n]=\sum _{k=0}^{n}a[k] \end{gathered}$$

通过递推公式可快速推导：原数组任意区间 （0下标，包含两端）的元素和 =$pre[r]-pre[l-1]$ 。特殊地，当 $l=0$ 时，区间和直接等于 $pre[r]$。

经典模板题

题目描述：给定长度为 $x$ 的数组 $a$，以及 $n$ 次区间查询，每次给出区间 $[l,r]$，求数组第 $l$ 项到第 $r$ 项的区间和，逐行输出每次查询结果。

输入格式：

第一行：$x,n$（数组长度、查询次数）

第二行：$a_1,a_2,\dots ,a_x$（数组元素）

后续 $n$ 行：每行两个数 $l_i,r_i$（查询区间）

数据范围：$0\le l\le r\le x\le 10^5$，$0<n\le 10^5$

代码模板

代码路径：1/prefix_sum.cpp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int a[maxn], pre[maxn];

int main()
{

ios::sync_with_stdio(false);
cin.tie(nullptr);

int x, n;
cin >> x >> n;

// 读入原数组
for (int i = 0; i < x; i++)
{

cin >> a[i];
}

// 预处理前缀和数组
pre[0] = a[0];
for (int i = 1; i < x; i++)
{

pre[i] = pre[i – 1] + a[i];
}

// 处理n次区间查询
int l, r;
for (int i = 0; i < n; i++)
{

cin >> l >> r;
// 适配0下标区间求和公式
if (l == 0) cout << pre[r] << \”\\n\”;
else cout << pre[r] – pre[l – 1] << \”\\n\”;
}
return 0;
}

1.1.2 差分算法

差分算法是区间批量修改专用的高效预处理算法，核心场景为：对数组多次执行「区间统一加/减固定数值」的操作，最后输出修改后的完整数组。

暴力区间修改的时间复杂度为 $O(m\cdot n)$，大数据量下极易超时；差分算法通过预处理差分数组，将整体复杂度优化至 $O(x+q)$，是区间批量更新题型的最优解。

算法核心简述

差分是前缀和的逆运算。基于原数组$a$（0下标）构建差分数组 $diff$，数组元素对应规则如下：

$$\begin{gathered} diff[0]=a[0] \\ diff[1]=a[1]-a[0] \\ diff[2]=a[2]-a[1] \\ \cdots \\ diff[i]=a[i]-a[i-1](i\ge 1) \end{gathered}$$

核心操作原理：对原数组区间 $[l,r]$ 统一增加数值 $q$，仅需对差分数组执行两步操作：

所有区间修改完成后，对 $diff$ 数组求一次前缀和，即可还原得到修改后的原数组。

手动推演示例

设原数组 a = { 1 , 5 , 3 , 7 , 8 , 2 , 4 } a = \\{1,5,3,7,8,2,4\\} a={
1,5,3,7,8,2,4}，构建初始差分数组： d i f f = { 1 , 4 , − 2 , 4 , 1 , − 6 , 2 } diff = \\{1,4,-2,4,1,-6,2\\} diff={
1,4,−2,4,1,−6,2}。

执行操作：对区间 $[2,4]$（0下标）所有元素加3。

经典模板题

题目描述：给定长度为 $x$ 的数组$a$，进行 $n$ 次区间修改操作，每次操作将区间 $[l,r]$ 内所有元素增加数值 $q$，最终输出修改后的完整数组。

输入格式：

第一行：$x,n$

第二行：$a_1,a_2,\dots ,a_x$

后续 $n$ 行：每行三个数 $l_i,r_i,q_i$

数据范围：同前缀和模板题，所有数据保证在 int 范围内。

代码模板（优化版）

代码路径：1/difference.cpp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int a[maxn], diff[maxn];

int main()
{

ios::sync_with_stdio(false);
cin.tie(nullptr);

int x, n;
cin >> x >> n;

// 读入原数组
for (int i = 0; i < x; i++)
{

cin >> a[i];
}

// 构建差分数组
diff[0] = a[0];
for (int i = 1; i < x; i++)
{

diff[i] = a[i] – a[i – 1];
}

// 批量处理区间修改操作
for (int i = 0; i < n; i++)
{

int l, r, q;
cin >> l >> r >> q;
// 转换为0下标
l—, r—;
diff[l] += q;
// r+1越界时无需抵消（无后续元素，不影响结果）
if (r + 1 < x)
diff[r + 1] -= q;
}

// 前缀和还原修改后的数组
for (int i = 1; i < x; i++)
{

diff[i] += diff[i – 1];
}

// 输出结果
for (int i = 0; i < x; i++)
{

cout << diff[i] << \” \”;
}
return 0;
}

1.1.3 算法小结

前缀和与差分是算法竞赛入门最基础、最实用的成对算法，二者互为逆运算，核心价值均为优化区间操作时间复杂度，彻底解决暴力解法的超时问题。

两种算法逻辑简洁、代码量小，是后续进阶算法（二维前缀和、差分约束等）的基础，必须熟练掌握模板与核心原理。

1.2 算法进阶应用

1.2.1 二维前缀和算法

二维前缀和与一维前缀和核心思想完全一致，均通过预处理实现区间查询$O(1)$，只是维度上升后需要借助容斥原理进行计算，逻辑更加复杂。

二维前缀和主要用于快速求取子矩阵元素和。给定大小为$n\times m$的矩阵，共$q$次子矩阵查询。暴力做法需要遍历整个子矩阵，时间复杂度$O(q\cdot S)$（$S$为子矩阵面积）；二维前缀和预处理复杂度$O(nm)$，单次查询仅$O(1)$。当矩阵规模、查询次数较大时，效率优势十分明显。

算法核心简述

定义二维前缀和数组 $pre[i][j]$：代表原矩阵左上角$(1,1)$到$(i,j)$围成矩形内所有元素之和。 $$pre[i][j]=\sum _{x=1}^i\sum _{y=1}^{j}a[x][y]$$

构建二维前缀和依赖容斥原理：

• $pre[i][j]$ = 当前位置原元素 $a[i][j]$
• 上方矩形和 $pre[i-1][j]$
• 左侧矩形和 $pre[i][j-1]$
• 左上角重复计算的矩形和 $pre[i-1][j-1]$

公式： $$pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]$$

完成预处理后，设目标子矩阵左上角$(x_1,y_1)$，右下角$(x_2,y_2)$，子矩阵和公式： $$sum=pre[x_2][y_2]-pre[x_1-1][y_2]-pre[x_2][y_1-1]+pre[x_1-1][y_1-1]$$

原理：

经典模板题

题目描述：给定一个 $n$ 行 $m$ 列的整数矩阵，一共有 $q$ 次询问。每次询问给出四个整数 $x_1,y_1,x_2,y_2$，求矩阵中第 $x_1$ 行至第 $x_2$ 行、第 $y_1$ 列至第 $y_2$ 列围成矩形内所有数字的总和，分行输出。

输入格式 第一行三个整数 $n,m,q$，代表矩阵行数、列数、询问次数。 接下来 $n$ 行，每行 $m$ 个整数，表示矩阵元素。 接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，保证 $1\le x_1\le x_2\le n,1\le y_1\le y$