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

【刷题6】一维前缀和、二维前缀和

目录

  • 一、一维前缀和
  • 二、二维前缀和

一、一维前缀和

题目:
在这里插入图片描述
思路:
在这里插入图片描述
一、前缀和,时间复杂度O(1),快速得到区间的值
二、预处理,公式——dp[i] = dp[i-1] + arr[i]
三、使用前缀和,根据题目计算出区间
四、多开一个好放数据,同时满足l、r下标刚好对应上

代码:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> arr(n+1);
    for(int i=1; i<=n; i++) cin >> arr[i];
    // 预处理前缀和数组
    vector<long long> dp(n+1);
    for(int i=1; i<=n; i++) dp[i] = dp[i-1] + arr[i];
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        // 使用前缀和数组
        cout << dp[r] - dp[l-1] << endl;
    }
}

二、二维前缀和

题目:
在这里插入图片描述
思路:
在这里插入图片描述
一、预处理前缀和矩阵
二、使用

代码:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> arr(n+1, vector<long long>(m+1));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin >> arr[i][j];
        }
    }
    // 预处理前缀和矩阵
    vector<vector<long long>> dp(n+1, vector<long long>(m+1));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];
        }
    }
    while(q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 使用
        long long ret = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
        cout << ret << endl;
    }
}

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

相关文章:

  • H265编码丢帧问题分析
  • 408——计算机网络(持续更新)
  • kafka里的consumer 是推还是拉?
  • ElasticSearch学习篇16_《检索技术核心20讲》进阶篇之空间检索
  • CloudCompare——基于连通性的点云分类【2024最新版】
  • 【AIGC】如何充分利用ChatGPT:有效提示框架与基本规则
  • 学习VTK的目的和方法
  • 速盾:cdn加速什么好?
  • 【Linux探索学习】第二弹——Linux的基础指令(中)——夯实基础第二篇
  • 25考研咨询周开启,西安电子科技大学是否改考408??
  • HarmonyOS Next系列之水波纹动画特效实现(十三)
  • ClickHouse入库时间与实际相差8小时问题
  • 升级FreeBSD13.2到14.1-RELEASE
  • 树和二叉树知识点大全及相关题目练习【数据结构】
  • golang 获取证书的生效及过期时间
  • 【论文笔记】Flamingo: a Visual Language Model for Few-Shot Learning
  • Redis篇(应用案例 - 附近商户)(持续更新迭代)
  • Pgsql 数据库操作
  • 【运动控制】关于GPIO通用输入口是NPN型数字输入
  • Grafana指标汉化
  • 【测试-BUG篇】软件测试的BUG知识你了解多少呢?
  • 自动驾驶系列—DOW(开门预警):让每一次开门都更安心
  • 水囊在消防灭火工作中的作用
  • 机器人的性能指标
  • C++ | Leetcode C++题解之第448题找到所有数组中消失的数字
  • 使用 pypdf 给 PDF 添加目录书签