前缀和、差分
前缀和、差分
前缀和可以快速求区间和。
差分相当于前缀和的逆运算。
前缀和、差分都是以空间换时间的算法
前缀和
定义
前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。
一维前缀和
题目一
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main(){
int n, m;
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
scanf("%d", &m);
while(m -- ){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
题目二
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main(){
int n, m, l, r;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
while(m -- ){
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
二维前缀和
题目一
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, q;
int a[N][N];
int main(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
scanf("%d", &a[i][j]);
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
int x1, y1, x2, y2;
while(q -- ){
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]);
}
return 0;
}
题目二
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 2;
int s[N][N];
int main(){
int n, m, x, y, v;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++ ){
scanf("%d%d%d", &x, &y, &v);
x ++ , y ++ ;
s[x][y] += v; // 每个攻击目标都具有v价值,攻击目标有可能重复
}
for(int i = 1; i < N; i ++ ){
for(int j = 1; j < N; j ++ ){
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int res = 0;
for(int i = m; i < N; i ++ ){
for(int j = m; j < N; j ++ ){
res = max(res, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);
}
}
printf("%d", res);
return 0;
}
差分
定义
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
一维差分
题目一
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main(){
int n, m, l, r, c, t;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ){
scanf("%d", &t);
a[i] += t; // 求差分数组, 相当于b[i] = a[i] - a[i - 1];
a[i + 1] -= t;
}
while(m -- ){
scanf("%d%d%d", &l, &r, &c);
a[l] += c;
a[r + 1] -= c;
}
for(int i = 1; i <= n; i ++ ){
a[i] += a[i - 1];
printf("%d ", a[i]);
}
}
题目二
Luogu P4552 [Poetize6] IncDec Sequence
TODO
二维差分
题目一
TODO