差分

差分是前缀和的逆运算

例题：

输入一个长度为n的整数序列。

接下来输入 $m$ 个操作，每个操作包含三个整数 $l, r, c，$表示将序列中 $[l, r]$ 之间的每个数加上 $c$。

请你输出进行完所有操作后的序列。

(输入输出格式以及数据范围就不贴了)

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int vals[N];

void myinsert(int l, int r, int val)
{
	vals[l] += val, vals[r + 1] -= val;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		int val;
		scanf("%d", &val);
		myinsert(i, i, val);
	}
	while (m--)
	{
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		myinsert(l, r, c);
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		res += vals[i];
		printf("%d ", res);
	}
	return 0;
}

一开始输入的数组被看作一个前缀和数组。一开始使用 $myinsert(i, i, val)$ 构造出了一个新数组，这个新数组的前缀和是原数组。直接对原数组一个区间上的一次修改操作是 $O(n)$ 的，现在对新数组修改一次是 $O(1)$ 的；最终结果则是新数组求一次前缀和就能得到答案结果数组。