差分

思路

差分就是求前缀和的逆运算，就是bn=an-a(n-1),a是b的前缀和，这样处理是为了我们更好的处理在i~j个区间内对每一个a都加c的操作，利用b[i]+c,b[j+1]-c的操作来实现以上的要求，不懂的举个例子就知道了。

代码

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
const int N = 100010;

int b[N];

int main() {
	int n, m;
	cin >> n >> m;
	int t=0;//用t来存上一个a
	for (int i = 1; i <= n; i++) {//求出b
		int x;
		cin >> x;
		b[i] = x - t;
		t = x;
	}
	for (int i = 1; i <= m; i++) {//处理b
		int begin,end,x;
		cin >> begin >> end >> x;
		b[begin] += x;
		b[end + 1] -= x;
	}
	t = 0;
	for (int i = 1; i <= n; i++) {//对b求和以求出a
		t += b[i];
		cout << t << " ";
	}
}**