当前位置: 首页 > article >正文

蓝桥杯好题推荐---前缀和

🌈个人主页: 羽晨同学-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)的时间复杂度对元素进行查询。

 好了,今天的内容就到这里,我们明天再见。


http://www.kler.cn/a/589223.html

相关文章:

  • 深度学习篇---Opencv中的Haar级联分类器
  • MyBatis注解
  • Github 2025-03-16 php开源项目日报 Top10
  • 未来社交媒体的发展趋势:TikTok 与虚拟现实的结合
  • CCF-CSP第34次认证第四题——货物调度【DP+剪枝】
  • 零基础使用鸿蒙NDK开发最简步骤
  • KVM安全模块生产环境配置与优化指南
  • 【模拟面试】计算机考研复试集训(第四天)
  • 工程化与框架系列(35)--前端微服务架构实践
  • 【2025年39期免费获取股票数据API接口】实例演示五种主流语言获取股票行情api接口之沪深指数最新分时MACD数据获取实例演示及接口API说明文档
  • Spring 扩展点总结与分析
  • 【论文笔记】FFA-Net: Feature Fusion Attention Network for Single Image Dehazing
  • Spring MVC源码分析の请求处理流程
  • 从过拟合到强化学习:机器学习核心知识全解析
  • R 语言科研绘图 --- 密度图-汇总
  • C/C++基数排序(Radix Sort) 的排序算法。
  • 深入理解TCP/IP网络模型及Linux网络管理
  • Solidity基础 -- 哈希算法
  • C++ QT零基础教学(二)
  • tomato靶场通关攻略