devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

前缀和【算法】_前缀和算法

作者：知新_RL | 2024-04-09 17:59:27

赞

踩

前缀和算法

目录

一、一阶前缀和

          洛谷 P1147 连续自然数和

二、二维前缀和

        洛谷 P1719 最大加权矩形

一、一阶前缀和

定义：sum[i]:是数组0~数组i的和

例：一个数组：1,3,7,5,2

它的前缀和数组为:1,4,11,16,18

前缀和数组：数组中的位置i的值是数组0~i之间的和

作用：可以用于快速求数组区间的和(尤其是多次操作)

例：求数组arr的区间（l，r）的和ans
 

  1. //核心代码：
  2.  
  3. sum[0]=arr[0];
  4.  
  5. for(int i=1;i<n;i++)
  6.  
  7. sum[i]=sum[i-1]+arr[i]; //此时sum数组存储的前缀和
  8.  
  9. ans=sum[r]-sum[l-1]; //(l>0)
  10.  
  11. ans=sum[r]; //l=0

例：arr[5]={1,3,7,5,2};

求区间: (2,4),(0,3),(3,4)三个区间的区间和

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int n=5;
  4. int arr[n]={1,3,7,5,2};
  5. int sum[n];
  6. void get_sum()  //前缀和 
  7. {
  8.     sum[0]=arr[0]; 
  9.     for(int i=1;i<n;i++)
  10.     sum[i]=sum[i-1]+arr[i];
  11. }
  12. int add(int l,int r) //对区间（l,r）求和
  13. {
  14.     if(l==0)  return  sum[r]; //如果l=0，说明此时只需要求(0,r)之间的数字和，也就是此时的sum[r]
  15.     return sum[r]-sum[l-1]; //如果l>0，说明求的是(l,r)之间的和，也就是需要将sum[r]减去sum[l-1]
  16. //因为sum[r]存储的是0~r之间的数字和,sum[l]存储的是0~l之间的数字和；
  17. }
  18. int main(int argc, char** argv) {   //没有一点技术含量的主函数
  19.     get_sum();
  20.     cout<<add(2,4)<<endl;
  21.     cout<<add(0,3)<<endl;
  22.     cout<<add(3,4)<<endl; 
  23.     return 0;
  24. }

洛谷 P1147 连续自然数和

题目描述

对一个给定的自然数M，求出所有的连续的自然数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为M。

例子：1998+1999+2000+2001+2002 = 100001998+1999+2000+2001+2002=10000，所以从19981998到20022002的一个自然数段为M=10000M=10000的一个解。

输入格式

包含一个整数的单独一行给出M的值（10≤M≤2,000,000）。

输出格式

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

输入输出样例

输入 

10000

输出

18 142 
297 328 
388 412 
1998 2002

 此题可以使用多种解法，如暴力枚举、尺取法、前缀和法， 在此使用的是前缀和法。

AC代码：

  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. long long sum[2000001]; 
  5. int main(int argc, char** argv) {
  6.     long long  n;
  7.     cin>>n;
  8.     for(int i=1;i<=n;i++) //计算前缀和，并存入数组sum中
  9.     sum[i]=sum[i-1]+i;
  10.     for(int l=1;l<=n;l++)//通过标记查找，符合结果的数
  11.     {
  12.         //标记mid=sum[l-1]+n,在sum数组中查找；
  13.         //因为区间(l,r)的区间和n=sum[r]-sum[l-1]；此时需要寻找的是r和l-1
  14.         //从0开始遍历数组，遍历的作为左区间l,此时可以通过sum[l-1]+n=sum[r]来寻找右区间r
  15.         auto mid=sum[l-1]+n;  //auto关键字可以自动识别变量的类型
  16.         auto r=lower_bound(sum,sum+n+1,mid)-sum;
  17.         //lower_bound函数是在指定区间内查找不小于mid的第一个元素
  18.         if(sum[r]-sum[l-1]==n)//此时sum[a]=sum[i-1]+n
  19.         {
  20.             if(l!=r)
  21.             cout<<l<<" "<<a<<endl;
  22.         }
  23.     }
  24.     return 0;
  25. }

【题目描述】 给定n个整数a1,a2,…,an，求他们两两相乘再相加的和。

即： S = a1•a2 + a1•a3 + ... + a1•an + a2•a3 + ... +  an-2•an-1 + an-2•an + an-1•an

【输入描述】 第一行包含一个整数n，第二行包含n个整数a1,a2,…,an。

【输出描述】输出一个整数S，表示所求的和。使用合适的数据类型进行运算。

【输入样例】   4        

                  1  3  6  9                                                

【输出样例】    117

【评测用例规模与约定】

对于30%的数据，1≤n≤1000，1≤ai≤100。 对于所有评测用例，1 ≤n≤200000，1≤ai≤1000。

思路分析：

从题目中可以看出有些式子都是由一个共同的公因式，将它提到外面可以得到下面的式子：

S = (a1+a2 +...+an-1)•an + (a1+a2 +...+an-2)•an-1  +(a1+a2 +...+an-3)•an-2 + ...+(a1+a2)•a3 + a1•a2

在这个中，我们可以发现，括号里面的数可以使用前缀和来实现。

即：sum[i] = a1+ a2+…+ ai

则上式可以改成：

S = sum[n-1] •an + sum[n-2]•an-1 + sum[n-3]•an-2 + ... + sum[2]•a3 + sum[1]•a2

前缀和只用到sum[1]~sum[n-1]

AC代码：

  1. #include <iostream>
  2. using namespace std; 
  3. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  4. const int N = 200005;
  5. int a[N];
  6. long long sum[N];//前缀和数组,因为去和数字有点大，记得开long long 
  7. int main(int argc, char** argv) {
  8. 	int n;
  9. 	cin>>n;
  10. 	sum[1]=0;//将sum[0]置为0 
  11. 	for(int i=1;i<=n;i++)
  12. 	{
  13. 		cin>>a[i];
  14. 		sum[i]=sum[i-1]+a[i];//计算前缀和	
  15. 	} 
  16. 	long long ans=0;//存储答案 
  17. 	for(int i=1;i<=n;i++)
  18. 	{
  19. 		ans+=sum[i]*a[i+1];//当i等于n时,sum[n]*a[n+1]=0(a[n+1]=0),所以没有用到sum[n] 
  20. 	}
  21. 	cout<<ans;
  22. 	return 0;
  23. }

二、二维前缀和

               一维前缀和只能用于一维的数据结构求和（如数组），二维前缀和则是在二维数据结构上求和（如矩阵）。

定义：求矩阵g[0,0]到[i,j]的值的和
          sum[i][j]:是矩阵g[0][0]到g[i][j]的二维前缀和（存放二维前缀和）
          g[i][j]是该矩阵i行j列的值（存放原矩阵）

性质：sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]; 

作用：求矩阵区间：[x1][y1]~[x2][y2]的区间和ans（尤其是多次询问操作） 

核心代码：

  1.   ans=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
  2.     //此公式可以进行画图理解
  3.   /* ps:如果i=0，ans=sum[x2][y2]-sum[x1-1][y2]; 
  4.          如果j=0, ans=sum[x2][y2]-sum[x2][y1-1]; 
  5.          如果i=0,j=0, ans=sum[x2][y2]; 
  6.     ps:当i=0/j=0时，可以将其看成一维数组进行前缀和进行计算 
  7.     sum[0][j]=sum[0][j-1]+g[0][j];
  8.     sum[i][0]=sum[i-1][0]+g[i][0]    
  9.    */

例：
矩阵：     1,5,6,8
                9,6,7,3
                5,3,2,4
 1、求出二维前缀和sum
 2、求区间（[1][1]~[2][2]）的和 
答案：
    二维前缀和sum:
    1 6 12 20
    10 21 34 45
    15 29 44 59
[1][1]~[2][2]区间和为：18 

AC代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int n=3,m=4;
  4. int g[n][m]={ {1,5,6,8},
  5.               {9,6,7,3},
  6.               {5,3,2,4}};     //原矩阵 
  7. int sum[n][m];  //存放二维前缀和 
  8. void pre_sum()  //求二维前缀和 
  9. {
  10.     sum[0][0]=g[0][0]; //前一个直接存放
  11.     for(int j=1;j<=m;j++)  sum[0][j]=sum[0][j-1]+g[0][j]; //第一行
  12.     for(int i=1;i<=n;i++)  sum[i][0]=sum[i-1][0]+g[i][0]; //第一列
  13.     for(int i=1;i<n;i++)  //其它 
  14.     for(int j=1;j<m;j++)
  15.     sum[i][j]=sum[i-1][j]+sum[i][j-1]+g[i][j]-sum[i-1][j-1]; 
  16.  } 
  17.  int get_sum(int x1,int y1,int x2,int y2)  //求区间和 
  18.  {
  19.        if(x1==0&&y1==0)        return sum[x2][y2]; //求的就是sum[x2][y2]的前缀和
  20.         if(x1==0)                   return sum[x2][y2]-sum[x1-1][y2];
  21.         if(y1==0)                        return sum[x2][y2]-sum[x2][y1-1];
  22.     return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
  23.  }
  24. int main(int argc, char** argv) {
  25.     pre_sum();
  26.     cout<<"二维前缀和sum:";
  27.     for(int i=0;i<n;i++)
  28.     {
  29.        cout<<endl;
  30.     for(int j=0;j<m;j++)
  31.      cout<<sum[i][j]<<" ";
  32.     }
  33.            cout<<endl;
  34.     cout<<"区间和为：" ; 
  35.     cout<<get_sum(1,1,2,2)<<" ";
  36.     return 0;
  37. }
  38.  
  39. ​​

洛谷 P1719 最大加权矩形

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个n×n 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于 [-127,127][−127,127] ,例如

  1.  0 –2 –7  0 
  2.  9  2 –6  2
  3. -4  1 –4  1 
  4. -1  8  0 –2

在左下角：

  1. 9  2
  2. -4  1
  3. -1  8

和为 15。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：n，接下来是 n 行 n 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

输入输出样例

输入

4
0 -2 -7 0
 9 2 -6 2
-4 1 -4  1 
-1 8  0 -2

输出 

15

说明/提示

1≤n≤120

  1. #include <iostream>
  2. using namespace std;
  3. int n;
  4. int a[137][137];  //原矩阵
  5. int sum[137][137]; //存放二维前缀和 
  6. int main(int argc, char** argv) {
  7. 	int n;
  8. 	cin>>n;
  9. 	for(int i=1;i<=n;i++)
  10. 	{
  11. 		for(int j=1;j<=n;j++)
  12. 		{
  13. 			cin>>a[i][j];
  14. 			sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];  //计算二维前缀和，并存入sum数组 
  15. 		}
  16. 	 } 
  17. 	 int mx=-9999999999; //寻找最大值，先定义一个最小值 
  18. 	 for(int x1=1;x1<=n;x1++) //对矩阵进行遍历 
  19. 	 {
  20. 	 	 for(int y1=1;y1<=n;y1++)
  21. 	 	 {
  22. 	 	 	 for(int x2=1;x2<=n;x2++)
  23. 	 	 	 {
  24. 	 	 	 	 for(int y2=1;y2<=n;y2++)
  25. 	 	 	 	 {
  26. 	 	 	 	 		 if(x2<x1||y2<y1)	//必须符合x2>x1,y2>y1才可以 
  27. 							  continue;
  28. 	 	 	 	 mx=max(mx,sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]); //寻找子区间的最大值 
  29. 			   	 }
  30. 			 }
  31. 		  }
  32. 	  } 
  33. 	 cout<<mx;
  34. 	return 0;
  35. }

掌握了基本前缀和的算法，你一定非常想要使用它来获取AC的快感吧。下面贴出了洛谷平台的前缀和题单，你确定不来试试吗？

前缀和题目传送门

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/394328
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号