前缀和和差分

前缀和

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 100008;
int s[N];
int a[N];

signed main () {
	int n,m;
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	while(m--){
		int l,r;
		scanf("%lld %lld",&l,&r);
		printf("%lld\n",s[r]-s[l-1]);
	}
	


	return 0;
}

子矩阵的和

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 1004;
int s[N][N];
int a[N][N];

signed main () {
	int n, m, q;
	scanf("%lld %lld %lld", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
	while (q--) {
		int x1, y1, x2, y2;
		scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
		printf("%lld\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
	}

	return 0;
}

差分

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 1004;
int b[N];
int a[N];
void insert(int l, int r, int x) {
	b[l] = b[l] + x;
	b[r + 1] = b[r + 1] - x;
}

signed main () {
	int n, m;
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		insert(i, i, a[i]);
	}
	int l, r, x;
	while (m--) {
		scanf("%lld %lld %lld", &l, &r, &x);
		insert(l, r, x);
	}
	for (int i = 1; i <= n; i++) {
		b[i] = b[i - 1] + b[i];
	}
	for (int i = 1; i <= n; i++) {
		printf("%lld ", b[i]);
	}



	return 0;
}

差分矩阵

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 1004;
int b[N][N];
int a[N][N];
void insert(int x1, int y1, int x2, int y2, int x) {
	b[x1][y1] += x;
	b[x2 + 1][y1] -= x;
	b[x1][y2 + 1] -= x;
	b[x2 + 1][y2 + 1] += x;


}

signed main () {
	int n, m, q;
	scanf("%lld %lld %lld", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			insert(i, j, i, j, a[i][j]);
		}
	}
	int x1, y1, x2, y2, x;
	while (q--) {
		scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &x);
		insert(x1, y1, x2, y2, x);
	}
	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] + b[i][j];
			//	s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			printf("%lld ", b[i][j]);
//				b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
			//	s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
		printf("\n");
	}





	return 0;
}