网站建设排行榜,网站开发 集成包,泰州百度seo,公众号软文推广0x03前缀和、差分 文章目录 0x03前缀和、差分一维前缀和二维前缀和差分一维差分二维差分 习题T1T2T3 一维前缀和
数组前n项和 s [ k ] ∑ i 1 k a [ i ] s[k]\sum_{i1}^ka[i] s[k]∑i1ka[i]
s[i]s[i-1]a[i];二维前缀和
设s[i][j]表示以(1#xff0c;1)为顶点#xff0…0x03前缀和、差分 文章目录 0x03前缀和、差分一维前缀和二维前缀和差分一维差分二维差分 习题T1T2T3 一维前缀和
数组前n项和 s [ k ] ∑ i 1 k a [ i ] s[k]\sum_{i1}^ka[i] s[k]∑i1ka[i]
s[i]s[i-1]a[i];二维前缀和
设s[i][j]表示以(11)为顶点以(ij)为右下角的矩形内部权值之和。
即 s [ n ] [ m ] ∑ i 1 n ∑ j 1 m a [ i ] [ j ] s[n][m]\sum_{i1}^{n}\sum_{j1}^ma[i][j] s[n][m]∑i1n∑j1ma[i][j]
设a[i][j]为(i,j)点的权值。
那么s[i][j]可以表示为
s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];假如我们要求矩阵中 R x R 的矩形的权值和:
ans s[iR][jR]-s[i-1][jR]-s[iR][j-1]s[i-1][j-1];差分
差分--------原数组-------前缀和
原数组是差分和前缀和的中转站。
一维差分
b[i]a[i]-a[i-1]显然将b[i]累加起来就是a[i]
故有 ∑ i 1 j b [ i ] a [ j ] \sum_{i1}^jb[i]a[j] ∑i1jb[i]a[j]
所以
for(int i1;in;i){b[i]b[i-1];
}累加之后b[i]就等于a[i].
故如果我们需要对一个区间进行增减同一个数x的操作
只需要对这个区间的差分数组进行单点修改。
例如我们需要将[2,5]内的元素全部都增加1
只需要让b[2]1, b[6]-1 即可。
二维差分 ∑ i 1 n ∑ j 1 m b [ i ] [ j ] a [ i ] [ j ] \sum_{i1}^n\sum_{j1}^mb[i][j]a[i][j] ∑i1n∑j1mb[i][j]a[i][j]
当我们要对一个矩阵中的某一块区域进行加减同一个数x的操作的时候
例如将如下这个区间所有元素加上1 差分数组
其实和一维差分差不多。 习题
T1
99. 激光炸弹 - AcWing题库
普通的二维前缀和如果为了节省空间的话可以用前缀和数组和原数组公用一个数组。
#includebits/stdc.h
using namespace std;
const int N 500010;
typedef long long ll;
int sum[N][N] { 0 };
int main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n;int R;cin n R;Rmin(5001,R);R--;memset(sum, 0, sizeof sum);for (int i 1; i n; i) {int x, y, v;cin x y v;x;y;sum[x][y] v;}for (int i 1; i 50001; i) {for (int j 1; j 50001; j) {sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i-1][j-1];}}int ans 0;for (int i 1; i 50001; i) {for (int j 1; j 50001; j) {if(iR5001 or jR5001)continue;ans max(ans, sum[iR][jR] - sum[i-1][jR] - sum[iR][j-1] sum[i-1][j-1]); }}cout ans;
}T2
100. 增减序列 - AcWing题库
差分的经典用途将某一个区间[l,r]内的数增减同一个数x。
只需要在其差分数组上b[l] 减去1 b[r1]加上1
所以只对其差分数组中的两个点进行修改。
理论上如果一个序列中的所有的数是一样的话那么其差分数组
除第一项以外其余的都是0.
所以我们只需要修改 b[2]~b[n]中的任意两项使b[2]~b[n]都为0
计算 b[2]~b[n]中正数和p、负数和的绝对值q。然后取最小的抵消。此时剩下p-q
进行的操作是min(p,q)
然后剩下的数与b[1]或b[n1]进行操作。
1、如果b[1]有操作,那么b[1]只可能会被操作 1~p-q次
所以有 p-q种可能
2、如果b[1]无操作说明p-q次操作都在b[n1]上那么有1种情况
总共就是p-q1 种情况
总操作数max(p,q)
#includebits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lson pos1
#define rson (pos1)|1
const int N 1e57;
typedef long long ll;
ll a[N];
ll b[N];
int main() {ios;int n;cinn;for(int i1;in;i)cina[i];for(int i1;in;i)b[i]a[i]-a[i-1];ll zsum0;ll fsum0;for(int i2;in;i){if(b[i]0)zsumb[i];if(b[i]0)fsumb[i];}fsum-fsum;int ansmax(zsum,fsum);int bnsabs(zsum-fsum);coutansendlbns1;} T3
101. 最高的牛 - AcWing题库
差分的另一种运用我们一开始假设这些牛一样高
若 l、r 能互相看见说明 l、r 之间的数都需要-1
然后最终的答案就是最大身高。
为了减少时间复杂度我们用差分数组进行单点修改。
将a[l1]-1, a[r]1
然后求和然后每一项h即可
#includebits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
const int N5e37;
typedef long long ll;
mappairint,int,int mmp;int a[N];
int main() {ios;int n,p,h,m;cinnphm;// for(int i1;in;i)a[i]h;while(m--){int l,r;cinlr;if(lr)swap(l,r);if(mmp[pair(l,r)]0){mmp[pair(l,r)];a[l1]--;a[r];}}for(int i1;in;i){a[i]a[i-1];}for(int i1;in;i){a[i]h;}for(int i1;in;i)couta[i]endl;
}
