算法基础：差分

一维差分

本质

前缀和的逆运算
想要更容易搞懂差分，前提是要先搞懂前缀和如何求
前缀和链接

原理

有一数组a，b，使得 ai = b1 + b2 + b3 + … + bi

例如 b1 = a1

b2 = a2 - a1；

b3 = a3-a2

bn = an-a（n-1）；

b就称为a的差分，a就称为b的前缀和

使某一区域的前缀和被同步改变，

本质上是改变边界的值，使得中间连续值得以被间接改变

用处：且比原先（n）的时间复杂度优化为O（1）

例题模板

//改变a任意区间的前缀和，使该区间的前缀和+c，其他保持不变
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 10001;

int n, m;
int a[N];
int b[N];
//改变两边的值，使得中间连续值得以被间接改变，降低时间复杂度
void insert(int l, int r, int c)
{
	b[l] += c;
	b[r + 1] -= c;
}
int main()
{
	scanf("%d%d", &n, &m);
//获取前缀和即a数组
	for (int i = 1;i <= n;++i) scanf("%d", &a[i]);
//将前缀和赋给b，向b数组插入元素，假设前缀和皆为0
	for (int i = 1;i <= n;++i) insert(i, i, a[i])；
//改变区间内的前缀和
	while (m--)
	{
		int l, r, c;
		scanf("%d%d%d", &l, & r, &c);
		insert(l, r, c);
	}

	for (int i = 1;i <= n;++i) b[i] += b[i - 1];
	for (int i = 1;i <= n;++i) printf("%d ", b[i]);

	return 0;
}

二维差分

本质

与一维差分相同，也是前缀和的逆运算

原理

假设要改变存储前缀和的二维数组中特定矩阵发生改变

则使存储前缀和的二维数组某一坐标的右下角全部改变，并使多余部分减掉，由于需改变矩阵的右下角的矩阵被减掉两次，还需要使其重新加回来，成为原本的前缀和，从而得到一个存储前缀和的矩阵中特定的小矩阵发生改变

用处

降低原先笨方法的时间复杂度

模板

//改变二维前缀和中的特定矩阵元素
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstdio>
const int N = 1001;

int n, m, q;
int a[N][N];
int b[N][N];
using namespace std;
//能使大矩阵中的特定矩阵发生改变
//如果端点处改变，其右下角的所有元素都会被间接改变
void insert(int x1, int y1, int x2, int y2, int c)
{
	//实现矩阵内的控制小矩阵元素
	b[x1][y1] += c;
	b[x2 + 1][y1] -= c;
	b[x2][y1 + 1] -= c;
	b[x2 + 1][y2 + 1] += c;
}
int main()
{
	scanf("%d%d", &n, &m, &q);
	//读入数据,获取前缀和即a数组
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j)
			scanf("%d", &a[i][j]);
	//初始化b数组
	for (int i = 1;i <= n;++i)
	{
		for (int j = 1;j <= m;++j)
			insert(i, j, i, j, a[i][j]);
	}
	while (q--)
	{
		int x1, y1, x2, y2,c;
		//控制特定矩阵的元素
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2,&c);
		insert(x1, y1, x2, y2, c);
	}
	//得出改变后的前缀和
	for (int i = 1;i <= n;++i)
	{
		for (int j = 1;j <= m;++j)
			b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
	}
	//打印输出
	for (int i = 1;i <= n;++i)
	{
		for (int j = 1;j <= m;++j)
			printf("%d ", b[i][j]);
		printf("\n");
	}
	return 0;
}