一、一维前缀和与一维差分
1.一维前缀和
什么是前缀和呢？
前缀和（Prefix Sum) 顾名思义就是构建一个新的数组，其中每个元素表示原始数组从起始位置到当前位置的累加和。是一种重要的数据预处理技术,这种通过空间换时间的思想，将区间求和的时间复杂度从O(n)降到O(1)，可以快速求出数组任意区间的和,是解决许多区间/子数组问题的利器。
- 相比较其他算法而言，前缀和更像是一种解题的技巧，一种优化方式。
引入
输入一个长度为n的整数序列，接下来再输入m个询问，每个询问输入一对l,r。对于每个询问，输出原序列中从第l个数到第r个数的和。
对于次问题，我们不难想到暴力法，代码如下：
const int N = 1e5 + 10; //科学计数法,即100010
int a[N];
int n,m;
cin >> n >> m; //输入n,m
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
while(m--)
{
int l, r;
int sum = 0;
cin >> l >> r;
for(int i = l; i <= r; i++)
{
sum += a[i];
}
cout << sum << endl;
}不难发现，这段代码的时间复杂度为O(n * m)，如果n和m的稍大一些，代码就会超时。
这时候我们如果想优化，可以使用一维前缀和。
首先做一个预处理，定义一个pref[n + 1]数组，pref[i]代表a数组中前i个数的和。
const int N = 1e5 + 10;
int pref[N], a[N]; //pref[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1;i <= n; i++)
{
pref[i] = pref[i - 1] + a[i];
}对于查询操作代码：
cin >> l >> r;
cout << pref[r] - pref[l-1] << endl;查询操作优化为cout << pref[r] – pref[l-1] << endl，可以参考下图理解。
一维前缀和时间复杂度：预处理O(n),查询O(1)，O(n + m)总时间复杂度为效率比较高效，后续也会有一些其他的解法，比如说线段树，树状数组等，前缀和的运行时间是最短的。
2.一维差分
差分（Difference）可以理解为前缀和的逆运算，就是将数列中每一项分别与前一项做差。
那么我们如何得到一维差分数组呢？
一维差分数组的有什么用处呢？
同样的，我们思考一个这样的问题：
有n个整数，给定m个区间[l, r ]，让我们把a数组中的[l, r] 区间中的每一个数都加上c，即 a[l] + c , a[l + 1] + c , a[l + 2] + c, …… ,a[r] + c，最后按顺序给出改变后的数组。
暴力法和之前的前缀和基本思路相同，同样的，问题是时间复杂度O(n * m)太高。
这时候我们要考虑差分做法。
a数组是diff数组的前缀和数组，对diff数组的diff[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分diff数组中的 diff[l] + c ，通过前缀和运算，a数组从下标l向后都多了一个我们添加的c，
即 a[l] + c ,a[l + 1] + c, …… ,a[n] + c;
然后我们把差分diff数组中的 diff[r + 1] – c通过前缀和运算，a数组从下标r向后减去一个c，
即 a[r + 1] – c,a[r + 2] – c, …… ,a[n] – c;
此时我们发现，对diff数组做前缀和得到的新数组即为仅改变区间l到r且改变量为c的数组。
因此我们得到结论：
要对数组区间 [ l, r ] 的数据都加上c时，我们只需要对差分数组进行操作即可。
- 即 l到前一个元素的距离+c，r到后一个元素的距离-c
diff[l] += c;
diff[r+1] -= c;这里给出核心代码：
// 核心1：构建差分数组
// diff[i] = a[i] - a[i-1]，其中diff[1] = a[1]（因为a[0]=0）
for (int i = 1; i <= n; ++i) {
diff[i] = a[i] - a[i - 1];
}
// 核心2：执行m次区间加操作
for (int i = 0; i < m; ++i) {
int l, r, c;
cin >> l >> r >> c;
// 差分数组的核心操作
diff[l] += c; // l位置加c，影响后面所有元素
diff[r + 1] -= c; // r+1位置减c，抵消r之后的影响
}
// 核心3：通过前缀和还原数组
// 对差分数组求前缀和，得到修改后的原数组
for (int i = 1; i <= n; ++i) {
diff[i] += diff[i - 1]; // 前缀和：当前值 = 前一个值 + 当前差值
cout << diff[i] << " ";
}
二、二维前缀和和二维差分
1.二维前缀和
二维前缀和（也称为积分图）是对二维数组（矩阵）的一种预处理方法，可以快速计算任意子矩阵的元素和。
引入
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
同一维前缀和一样，我们先来定义一个二维数组diff[n + 1][m + 1]。
diff[i][j] 表示二维数组中，左上角(1, 1)到右下角(i, j)所包围的矩阵元素的和。
那么二维前缀和的公式就是：pref[i][j] = pref[i – 1][j] + pref[i][j – 1 ] + a[i] [j] – pref[i – 1][j – 1]
可以借助下图理解记忆：
整个外围蓝色矩形面积pref[i][j]
= 绿色面积pref[i – 1][j] + 黄色面积pref[i][j – 1] + 小方块的面积a[i][j] – 重复加的红色的面积pref[i – 1][j – 1];
通过图例我们再次印证了上述二维前缀和公式的合理性与正确性。
有了以上基础，现在若要求某一区域的子矩阵和怎么办？
我们从图例中理解如何求以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和。
分析得出以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
pref[x2, y2] – pref[x1 – 1, y2] – pref[x2, y1 – 1] + pref[x1 – 1, y1 – 1]
下面给出以上子矩阵问题核心代码：
// 计算前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
}
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 计算子矩阵和，#define ll long long
ll sum = pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
cout << sum << endl;
}2.二维差分
二维差分是处理二维矩阵区间操作的高效工具，可以看作二维前缀和的逆运算。给定一个 m×n 的原始矩阵 A，其对应的二维差分矩阵 D 是一个 (m+2)×(n+2) 的矩阵,其中超出边界的 A[i][j] 视为 0。
对于一个给定的二维数组 a[][]，它的二维差分数组 diff[i][j] 可以用如下公式计算：
① diff[0][0]=a[0][0]
② diff[0][j]=a[0][j]-a[0][j – 1]
③ diff[i][0]=a[i][0]-a[i – 1][0]
④ 递推式：diff[i][j]=a[i][j]-a[i – 1][j]-a[i][j – 1]+a[i – 1][j – 1]
上述公式是通过二维数组 a[][]是二维差分数组的前缀和这个条件推导出来的。
借助图例理解：
diff[x₁][y₁] += c; // 对差分数组的更新，影响从(x1,y1)到右下角的整个区域
diff[x₁][y₂+1] -= c; // 对差分数组的更新，修正从(x1,y2+1)到右下角的区域
diff[x₂+1][y₁] -= c; // 对差分数组的更新，修正从(x2+1,y1)到右下角的区域
diff[x₂+1][y₂+1] += c; // 对差分数组的更新，修正从(x2+1,y2+1)到右下角的区域相关习题推荐我会抽时间具体研究然后列出来链接，我们只做精品，祝天天开心！
三、经典例题
1.一维前缀和
P1114 “非常男女”计划 – 洛谷
P1182 数列分段 Section II – 洛谷
2.一维差分
P1083 [NOIP 2012 提高组] 借教室 – 洛谷
