差分代码模板

#include
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], diff[N], prefix[N];//diff是差分 prefix是前缀
 
int main()
{
	//取消同步流
	//一般比scanf快 但是注意不要使用cout << endl; 改用 cout << '\n';
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) diff[i] = a[i] - a[i - 1];
 
	int m; cin >> m;
	while (m--)
	{
		ll l, r, x; cin >> l >> r >> x;
		diff[l] += x, diff[r + 1] -= x;//后缀区间修改
	}
	for (int i = 1; i <= n; ++i) a[i] = a[i-1] + diff[i];//求diff[i]前缀和还原a[i]
	for (int i = 1; i <= n; ++i) prefix[i] = prefix[i-1] + a[i];
 
	int q; cin >> q;
	while (q--)
	{
		ll l, r; cin >> l >> r;
		cout << prefix[r] - prefix[l - 1] << '\n';
	}
 
	return 0;
}