前缀和数组可以在O(1)的时间内求得某一区间中的所有数据的和
差分数组可以在O(1)的时间内对某一区间中的所有数据进行加减操作
原数组求差分及为差分数组，差分数组再求前缀和即为原数组
一维前缀和：
设原数组为
a[N]，前缀和数组为s[N]，数组下标都从1开始存储
每个s[i]等于a[1] + …… + a[i]
对于前缀和数组s[i]：
s[l - 1] = a[1] + a[2] + ... + a[l - 1]
s[l] = a[1] + a[2] + ... + a[l]
s[r] = a[1] + a[2] + ... + a[l] + ... + a[r]
那么
a[l ~ r] = s[r] - s[l - 1]
一维前缀和数组求法：
for (int i = 1; i <= n; i ++ )
s[i] = s[i - 1] + a[i];
如果为了节省空间，输入的数据直接保存在了s数组中，那么有：
for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
那么对于区间[l, r]中的数据的和，即为：s[r] - s[l - 1]
例题：前缀和
输入一个长度为 n的整数序列。
接下来再输入 m个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l个数到第 r个数的和。
输入格式
第一行包含两个整数 n和 m。
第二行包含 n个整数，表示整数数列。
接下来 m行，每行包含两个整数 l和 r，表示一个询问的区间范围。
输出格式
共 m行，每行输出一个询问的结果。
数据范围
1 ≤ l ≤ r ≤ n
1 ≤ n, m ≤ 1e5
−1000 ≤ 数列中元素的值 ≤ 1000
代码：
本题预处理前缀和数组的时间是O(n)，求每个区间和的时间是O(1)，一共的询问时间是O(m)
总时间复杂度为O(n + m)
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int s[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
一维差分：
cf[i] = a[i] - a[i - 1];
对于每个cf[i]：
cf[1] = a[1] - a[0];
cf[2] = a[2] - a[1];
cf[3] = a[3] - a[2];
...
cf[n] = a[n] - a[n - 1];
那么对cf数组求前缀和，就是原数组a
如果
cf[i] += 1，那么a[i]以及之后的元素都会加上1如果
cf[j] -= 1，那么a[j]以及之后的元素都会减去1因此如果我们想对区间
[l, r]中的所有的元素都加上x，那么有：
cf[l] += x, cf[r + 1] -= x;
作用：快速将某一区间[l, r]内的所有元素都加上数x
时间复杂度由O(n)变为了O(1)
差分数组求法：
设原数组为
a[N]，差分数组为cf[N]，数组下标都从1开始存储
先将差分数组初始化为0，memset(cf, 0, sizeof cf);
for (int i = 1; i <= n; i ++ )
cf[i] = a[i] - a[i - 1];
也可以在输入元素时分别插入每个元素：
void insert(int l, int r, int x)
{
cf[l] += x;
cf[r + 1] -= x;
}
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &temp);
insert(i, i, temp);
}
例题：差分
输入一个长度为 n的整数序列。
接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r]之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n和 m。
第二行包含 n个整数，表示整数序列。
接下来 m行，每行包含三个整数 l，r，c，表示一个操作。
输出格式
共一行，包含 n个整数，表示最终序列。
数据范围
1 ≤ n, m ≤ 100000
1 ≤ l ≤ r ≤ n
−1000 ≤ c ≤ 1000
−1000 ≤ 整数序列中元素的值 ≤ 1000
代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int cf[N];
void insert(int l, int r, int x)
{
cf[l] += x;
cf[r + 1] -= x;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
int temp;
scanf("%d", &temp);
insert(i, i, temp);
}
while (m -- )
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
insert(l, r, x);
}
// 求前缀和，将差分数组转换为原数组
for (int i = 1; i <= n; i ++ ) cf[i] += cf[i - 1];
for (int i = 1; i <= n; i ++ ) printf("%d ", cf[i]);
return 0;
}
二维前缀和：
设原数组为
a[N][N]，前缀和数组为s[N][N]，数组下标都从1开始存储
s[i][j]前缀和数组为从（0，0）到（i，j）区间中的元素和
将s[i][j]数组中区间元素和比作区间面积：
边界为（x1, y1）（x2, y2）的区域中的元素和即为区域4的面积s4，
可以发现：s4 = (s1 + s2 + s3 + s4) - (s1 + s3) - (s1 + s2) + s1
s1 + s2 + s3 + s4 = s[x2][y2]
s1 + s3 = s[x2][y1 - 1]
s1 + s2 = s[x1 - 1][y2]
s1 = s[x1 - 1][y1 - 1]
那么可以得出：
二维区间和：
a[x1 ~ x2][y1 ~ y2] = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
二维前缀和数组求法：
间接求：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
直接求：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
例题：子矩阵的和
输入一个 n行 m列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n行，每行包含 m个整数，表示整数矩阵。
接下来 q行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q行，每行输出一个询问的结果。
数据范围
1 ≤ n, m ≤ 1000
1 ≤ q ≤ 2e5
1 ≤ x1 ≤ x2 ≤ n
1 ≤ y1 ≤ y2 ≤ m
−1000 ≤ 矩阵内元素的值 ≤ 1000
代码：
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
printf("%d\n", res);
}
return 0;
}
二维差分：
设原数组为
a[N][N]，差分数组为cf[N][N]，数组下标都从1开始存储
和分析一维差分的方法类似，结合二维前缀和数组理解
cf[x1][y1] += 1使得原数组中的（x1, n）（y1，m）区间内的数全部加1
为了只使得特定区间(x1, y1)(x2, y2)中的数据加1，还需要抵消其他区间的影响
使得cf[x2 + 1][y1] -= 1, cf[x1][y2 + 1] -= 1, cf[x2 + 1][y2 + 1] -= 1
二维差分数组求法：
void insert(int x1, int y1, int x2, int y2, int x)
{
cf[x1][y1] += x;
cf[x2 + 1][y1] -= x;
cf[x1][y2 + 1] -= x;
cf[x2 + 1][y2 + 1] += x;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
int t;
scanf("%d", &t);
insert(i, j, i, j, t);
}
例题：差分矩阵
输入一个 n行 m列的整数矩阵，再输入 q个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n行，每行包含 m个整数，表示整数矩阵。
接下来 q行，每行包含 5个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n行，每行 m个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1 ≤ n, m ≤ 1000
1 ≤ q ≤ 1e5
1 ≤ x1 ≤ x2 ≤ n
1 ≤ y1 ≤ y2 ≤ m
−1000 ≤ c ≤ 1000
−1000 ≤ 矩阵内元素的值 ≤ 1000
代码：
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int cf[N][N];
void insert(int x1, int y1, int x2, int y2, int x)
{
cf[x1][y1] += x;
cf[x1][y2 + 1] -= x;
cf[x2 + 1][y1] -= x;
cf[x2 + 1][y2 + 1] += x;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
int t;
scanf("%d", &t);
insert(i, j, i, j, t);
}
while (q -- )
{
int x1, y1, x2, y2, x;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &x);
insert(x1, y1, x2, y2, x);
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
// cf数组的前缀和即为原数组
cf[i][j] += cf[i - 1][j] + cf[i][j - 1] - cf[i - 1][j - 1];
printf("%d ", cf[i][j]);
}
puts("");
}
return 0;
}