C++前缀和,差分
2022/1/30 20:06:11
本文主要是介绍C++前缀和,差分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一维前缀和
定义:对于一个数组a,前缀和s是通过第推求出部分和。s[i]=a[0]+…+a[i]
如:a[5]={1,3,2,1,5} prefixsum={1,4,6,7,12}
prefixsum[0]=a[0]=1
prefixsum[1]=prefixsum[0]+a[1]=1+3=4
prefixsum[2]=prefixsum[1]+a[2]=4+2=6
prefixsum[3]=prefixsum[2]+a[3]=6+1=7
prefixsum[4]=prefixsum[3]+a[4]=7+5=12
写法:
const int MAX=1e5+5;//定义常量用const int int a[MAX]={};//定义数组存储数据 int pre[MAX]={};//定义前缀和数组 a[0]=0; pre[0]=0; int n,i; cin>>n; for(i=1;i<n;i++) { cin>>a[i]; pre[i]=pre[i-1]+a[i]; }`
二维前缀和
定义:有一个二维数组a,求出二位前缀和为s[i][j]=s[i-1][j]+s[i][j-1]-s[i][j]+a[i][j]
如:数组a[3][3]
1 3 5
2 4 6
7 8 9
二位前缀和s[3][3]
1 4 9
3 10 21
10 25 45
写法:
const int MAX=1e5+5; int a[MAX][MAX]={};//定义数组存储数据 int pre[MAX][MAX]={};//定义前缀和数组 a[0][0]=0; pre[0][0]=0; int n,m,i,j; cin>>n>>m; for(i=1;i<n;i++) { for(j=1;j<m;j++) { cin>>a[i][j]]; pre[i][j]]=pre[i-1][j]+pre[i][j-1]-pre[i][j]+a[i][j]; }
一维差分
定义:对于一个数列Ai,Pi=Ai-A(i-1),则称Pi为Ai的差分数列
如:
数列a={1,1,2,4,0,8}
差分数列p={1,0,1,2,-4,8}
二维差分
定义:对数组a[i][j],差分数组p[i][j]=a[i][j]-a[i-1][j]-a[i][j]+a[i-1][j-1]
如:
数组a[3][3]
1 3 5
2 4 6
7 8 9
差分数列p[3][3]
1 2 2
1 0 0
5 -1 -1
这篇关于C++前缀和,差分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享