有哪些做网站的品牌,网站云服务器租用,wordpress上传至哪个目录,珠海注册公司前缀和
定义#xff1a;
前缀和是指某序列的前n项和#xff0c;可以把它理解为数学上的数列的前n项和#xff0c;而差分可以看成前缀和的逆运算。合理的使用前缀和与差分#xff0c;可以将某些复杂的问题简单化。
用途#xff1a;
前缀和一般用于统计一个区间的和
前缀和是指某序列的前n项和可以把它理解为数学上的数列的前n项和而差分可以看成前缀和的逆运算。合理的使用前缀和与差分可以将某些复杂的问题简单化。
用途
前缀和一般用于统计一个区间的和为的就是可以将区间和问题的时间复杂度降低从而节约时间
样例
假如说我们有一个数组数组里面有n个元素给你m个访问每次给你一个L和R问你L和R这个区间内的元素的和为多少
我们首先想到的暴力解法应该是每次调用一次for循环去遍历区间的元素然后求和但是这样的时间复杂度在最坏的情况下会达到O(n*m)的时间复杂度对于大数据来说这种肯定是要超时的因此我们可以用到我们的前缀和
首先我们可以用一个前缀和数组统计出现的和pre[ i ]放的就是在 i 之前的所有数的和每次询问只需要输出pre[ R ] - pre[ L - 1 ]即可时间复杂度为O(nm)这样就大大减小的时间复杂度
因此我们可以看到前缀和在多次求解区间和问题上的优势。
一维前缀和
在一维空间内的统计十分简单只需要设计一个一维pre数组即可
一维前缀和预处理公式 pre[i]pre[i-1]a[i]; 区间求解公式从L到R的区间 pre[R]-pre[L-1] 来看例题
P8218 【深进1.例1】求区间和 题解很标准的前缀和问题每次询问的都是一个区间的和那么我们直接用一维前缀和即可
#includebits/stdc.h
using namespace std;
int n;
int a[100005];
int m;
int pre[100005];
int l,r;int main()
{cinn;for(int i1;in;i){cina[i];pre[i]pre[i-1]a[i];}cinm;for(int i1;im;i){cinlr;coutpre[r]-pre[l-1]\n;}return 0;
}
二维前缀和
二维前缀和的计算是基于容斥原理的我们需要通过对矩阵面积的划分计算来的出二维前缀和的预处理公式和求和公式
预处理公式
我们通过这个图来了解二维前缀和的预处理公式首先我们将元素变成矩阵的一个一个的小方块我们看如何去求第i行第j列之前的面积首先我们的矩阵面积可以S(i-1,j)S(i,j-1)的面积之和但是多了一部分重叠部分S(i-1,j-1),并且加上额外的有下角元素a(i,j)因此我们的预处理公式就可以得出
pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]a[i][j]; 二维前缀和求和公式 也是将计算变为矩阵面积来看假如说我们想算从(a,b)到(i,j)的前缀和我们首先可以用整个的大面积( S(i,j) )的面积减去S(a-1,j)和S(i,b-1)但是通过容斥原理发现我们多减一部分那就是
S(a-1,b-1)因此我们就可以得出二维前缀和求和公式
pre[i][j]-pre[a-1][j]-pre[i][b-1]pre[a-1][b-1] 我们来看一道例题最大加权矩阵 这道题一眼就能看出来是二维前缀和但是由于数据比较小所以可以暴力枚举其范围总共四重循环计算其中前缀和的最大矩阵和最后输出即可
#includebits/stdc.h
using namespace std;int n;
int a[125][125];
int pre[125][125];signed main()
{cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]a[i][j];}}int ans-0x3f3f3f3f;for(int x11;x1n;x1){for(int y11;y1n;y1){for(int x2x1;x2n;x2){for(int y2y1;y2n;y2){ansmax(ans,pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]pre[x1-1][y1-1]);}}}}coutans;return 0;
}
P2004 领地选择 题解就是一个二维前缀和模版很简单直接写就OK了只需要记录其中的左上角坐标就OK
#includebits/stdc.h
using namespace std;
#define int long long
int n,m,c;
int a[1005][1005];
int pre[1005][1005];
int ans-0x3f3f3f3f3f3f3f3f;
int x,y;signed main()
{cinnmc;for(int i1;in;i){for(int j1;jm;j){cina[i][j];pre[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]a[i][j];}}for(int ic;in;i){for(int jc;jm;j){if(anspre[i][j]-pre[i-c][j]-pre[i][j-c]pre[i-c][j-c]){anspre[i][j]-pre[i-c][j]-pre[i][j-c]pre[i-c][j-c];xi;yj;}}}coutx-c1 y-c1;return 0;
} 前缀和的应用包括二分思想这里默认各位看官老爷都会
P1314 [NOIP2011 提高组] 聪明的质监员 题意就是说给你n个矿石然后这n个矿石都有自己的重量w以及其价值v我们有一种判断机制就是说给你m个区间范围每次给你一个左边界L和右边界R我们的计算机理是这个区间内的大于规定筛选重量W的数量乘以大于筛选重量的价值,然后将总的算出来的y累加到一起看看和规定的标准值S最小差多少输出最小的参数W
思路我们发现这题数据超大必然会有优化方法我们通过上面·的题意可以发现我们的参数设置的越大能过筛选的石头越少得到的y值越小设置的越小能筛选过的石头越多得到的y值越大,因此我们可以用二分二分的范围就是给的数据的石头的最小值到最大值但是我们还要扩增范围最小值减一最大值加二然后我们每次二分的就是参数W然后在计算过程中要用到前缀和优化我们要去记录出现的大于参数的矿石数目以及总价值然后我们去计算总的Y值Y值大于标准值S就说明我们的参数设置的小了要增大左边界要是小于标准值就说明我们的参数设置的太大了要缩小右边界
#includebits/stdc.h
using namespace std;
#define int long long
int n,m,s;
int w[200005];
int v[200005];
int l[200005],r[200005];
int maxn0;
int minn0x3f3f3f3f3f3f3f3f;
int sumn[200005];
int sumv[200005];
int ans0;//统计本次筛选的总价值
int mn0x3f3f3f3f3f3f3f3f;//统计最小差值
bool check(int mid)
{memset(sumn,0,sizeof(sumn));memset(sumv,0,sizeof(sumv));int ans0;//统计总的价值也就是y[i] for(int i1;in;i){if(w[i]mid){sumn[i]sumn[i-1]1;//统计能过筛查的数量sumv[i]sumv[i-1]v[i];//统计能过筛查的价值 }else{sumn[i]sumn[i-1];sumv[i]sumv[i-1];}}for(int i1;im;i){ans(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);}mnmin(mn,llabs(ans-s));if(anss)return true;return false;
}
signed main()
{cinnms;for(int i1;in;i){cinw[i]v[i];maxnmax(maxn,w[i]);//二分的上下边界 minnmin(minn,w[i]);}int left,right,mid;for(int i1;im;i){cinl[i]r[i];}leftminn-1,rightmaxn2;while(leftright){mid(leftright)/2;if(check(mid)){leftmid1;}else{rightmid-1;}}coutmn;return 0;
}
