前缀和和差分
前缀和
#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;
}