差分

例题: https://www.luogu.com.cn/problem/P2367

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>

using namespace std;
typedef long long ll;
int n, p, s[6000000], c[6000000], ans=INT_MAX;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
	cin >> n >> p;
	for (int i=1;i<=n;i++) {
		cin >> s[i];
	}
	for (int i=1;i<=n;i++) {
		c[i] = s[i] - s[i-1];
	}
	
	for (int i=1;i<=p;i++) {
		int x, y, z;
		cin >> x >> y >> z;
		c[x] += z;
		c[y + 1] -= z;
	}
	
	for (int i=1;i<=n;i++) {
		s[i] = s[i-1] + c[i];
		ans = min(ans, s[i]);
	}
	
	cout << ans;
	
    return 0;
}

二位差分(容斥原理)

例题: https://www.luogu.com.cn/problem/P3397

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>

using namespace std;
typedef long long ll;
int n, m, c[2000][2000], ans=INT_MAX;

// P3397
int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
	
	cin >> n >> m;

	for (int i=1;i<=m;i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		c[x1][y1]++;
		c[x2+1][y1]--;
		c[x1][y2+1]--;
		c[x2+1][y2+1]++;
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			c[i][j] += c[i-1][j] + c[i][j-1] - c[i-1][j-1];
			cout << c[i][j] << " ";
		}
		cout << endl;
	}
    return 0;
}