网站建设构思,西点培训学校,陕西省建设监理工程协会网站,移动终端的网站#x1f63d;PREFACE#x1f381;欢迎各位→点赞#x1f44d; 收藏⭐ 评论#x1f4dd;#x1f4e2;系列专栏#xff1a;算法#x1f4aa;种一棵树最好是十年前其次是现在1.什么是前缀和前缀和指一个数组的某下标之前的所有数组元素的和#xff08;包含其自身#x…PREFACE欢迎各位→点赞 收藏⭐ 评论系列专栏算法种一棵树最好是十年前其次是现在1.什么是前缀和前缀和指一个数组的某下标之前的所有数组元素的和包含其自身。前缀和分为一维前缀和以及二维前缀和。前缀和是一种重要的预处理能够降低算法的时间复杂度。可以快速地求出某一段的和。2.一维前缀和2.1 前缀和公式已知数组前缀和2.2 前缀和的作用而且前缀和时间复杂度预处理O(n),查询O(1)效率比较高效后续也会有一些其他的解法比如说线段树树状数组等前缀和的运行时间是最短的。【补】关于左端边界是1的选择我们会发现求l到r的和时用的是,类似于数学里面的数列此时令下标要l-10这就保证了不需要定义任何的变量使用起来比较简单2.3 习题前缀和#include iostream
using namespace std;
const int N1e510;
int n,m;
int a[N],s[N];
int main()
{scanf(%d %d,n,m);for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) s[i]s[i-1]a[i];//前缀和初始化while(m--){int l,r;scanf(%d %d,l,r);printf(%d\n,s[r]-s[l-1]);//区间和计算}return 0;}3.二维前缀和3.1 二维前缀和公式首先二维前缀和公式的成立是基于容斥定理的二维前缀和实际上就是二维数组上的前缀和了。一维数组的前缀和也是一个一维数组同样地二维数组的前缀和也是一个二维的数组。红色区域的和3.2 习题子矩阵的和这一子矩阵中的所有数之和为#include iostream
using namespace std;
const int N 1010;
int n,m,q;
int a[N][N],s[N][N];int main()
{scanf(%d %d %d,n,m,q);for(int i1;in;i)for(int j1;jm;j)scanf(%d,a[i][j]);for(int i1;in;i)for(int j1;jm;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(%d %d %d %d,x1,y1,x2,y2);printf(%d\n,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]s[x1-1][y1-1]);//算子矩阵的和}return 0;
}4.什么是差分类似于数学中的求导和积分差分可以看成前缀和的逆运算。5.一维差分5.1 习题差分a数组是b数组的前缀和数组比如对b数组的b[i]的修改会影响到a数组中从a[i]及往后的每一个数。首先让差分b数组中的 b[l] c ,a数组变成 a[l] c ,a[l1] c,,,,,, a[n] c;然后我们还需要补充b[r1] - c, a数组变成 a[r1] - c,a[r2] - c,,,,,,,a[n] - c;我们画个图理解一下这个公式的由来:#include iostream
using namespace std;
const int N 1e5 10;
int n, m;
int a[N], b[N];
int main()
{scanf(%d %d, n, m);for (int i 1; i n; i){scanf(%d, a[i]);b[i] a[i] - a[i - 1];//构建差分数组}int l, r, c;while (m--){scanf(%d %d %d, l, r, c);b[l] c;//将[l,r]之间的每个数都加上cb[r 1] - c;}for (int i 1; i n; i){a[i] b[i] a[i - 1];//前缀和运算printf(%d , a[i]);}return 0;
}5.2 时间复杂度的分析如果采用暴力方法用for循环l到r区间时间复杂度O(n)如果我们需要对原数组执行m次这样的操作时间复杂度就会变成O(n*m)。考虑差分做法可极大地降低复杂度。给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] c, b[r1] - c。时间复杂度为O(1), 大大提高了效率。6.二维差分6.1 习题差分矩阵#include iostream
using namespace std;
const int N1010;
int n,m,q;
int a[N][N],b[N][N];
int main()
{scanf(%d %d %d,n,m,q);for(int i1;in;i){for(int j1;jm;j){cina[i][j];//同时求二维差分矩阵b即将前缀和公式移项b[i][j]a[i][j]-a[i-1][j]-a[i][j-1]a[i-1][j-1];}}while(q--){int x1,y1,x2,y2,c;cinx1y1x2y2c;//差分数组的模拟b[x1][y1]c;b[x1][y21]-c;b[x21][y1]-c;b[x21][y21]c;}//根据二维差分数组b去求二维前缀和矩阵afor(int i1;in;i){for(int j1;jm;j){a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]b[i][j];}}for(int i1;in;i){for(int j1;jm;j){printf(%d ,a[i][j]);}printf(\n);}return 0;}
6.2 差分矩阵的模拟假定我们已经构造好了b数组类比一维差分我们执行以下操作来使被选中的子矩阵中的每个元素的值加上cb[x1][y1] c;
b[x1,][y21] - c;
b[x21][y1] - c;
b[x21][y21] c;每次对b数组执行以上操作等价于for(int ix1;ix2;i)for(int jy1;jy2;j)a[i][j]c;图解过程b[x1][ y1 ] c ; //让整个a数组中矩形面积的元素都加上了c。
b[x1,][y21]-c ; //让整个a数组中绿色矩形面积的元素再减去c使其内元素不发生改变。
b[x21][y1]- c ; //让整个a数组中紫色矩形面积的元素再减去c使其内元素不发生改变。
b[x21][y21]c; //让整个a数组中红色矩形面积的元素再加上c红色内的相当于被减了两次再加上一次c才能使其恢复。
