蓝桥杯好题推荐---前缀和
🌈个人主页: 羽晨同学-CSDN博客
💫个人格言:“成为自己未来的主人~”
题目链接
【模板】前缀和https://ac.nowcoder.com/acm/problem/226282
解题思路
这种题目是要求我们找到一个数组中从l到r的元素的和,查询Q次,这道题目中,我们最直观的做法,往往就是暴力枚举,但是这样子时间复杂度会超过允许的范围,所以我们使用前缀和的方法,所谓的前缀和,就是说,我们创建一个前缀和数组,在这个数组中,我们存放着从第一个元素,到这个元素的总和,这样的话,如果我们确定好了要查找的目标,那么直接使用r的数组的数字-l的数组的数字就好了。这样的话,我们就可以保证使用O(1)的时间复杂度来完成我们的任务。
代码实现
#include <iostream>
using namespace std;
const int N = 1e6+10;
int f[N];//前缀和数组
首先,我们定义一个前缀和数组。
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
f[i]=f[i-1]+x;
}
接下来,我们将从开始位置到i位置的所有元素的和存放到f[i]当中,这个开始元素其实最好从1位置开始,因为在开始的时候,i-1为0,就不用处理边界问题。
while(q--)
{
int l,r;cin>>l>>r;
cout<<f[r]-f[l-1]<<endl;
}
最后我们再进行Q次查询操作。
这个是我们的完整的代码。
#include <iostream>
using namespace std;
const int N = 1e6+10;
int f[N];//前缀和数组
int main()
{
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
f[i]=f[i-1]+x;
}
while(q--)
{
int l,r;cin>>l>>r;
cout<<f[r]-f[l-1]<<endl;
}
return 0;
}
前缀和最大的优点就是可以采用O(1)的时间复杂度对元素进行查询。
好了,今天的内容就到这里,我们明天再见。