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

前缀和相关题目记录(未完待续...)

1 前缀和

一维前缀和是指对于一个数组 a a a,我们定义一个新的数组 s s s,其中每个元素 s [ i ] s[i] s[i] 表示从数组开头到第 i i i 个元素的累加和:

s [ i ] = a [ 1 ] + a [ 2 ] + ⋯ + a [ i ] = ∑ j = 1 i a [ j ] s[i] = a[1] + a[2] + \cdots + a[i] = \sum_{j=1}^{i} a[j] s[i]=a[1]+a[2]++a[i]=j=1ia[j]

通过预处理前缀和数组 s s s,我们可以快速计算任意区间 [ l , r ] [l, r] [l,r] 的和:

sum ( l , r ) = s [ r ] − s [ l − 1 ] \text{sum}(l, r) = s[r] - s[l - 1] sum(l,r)=s[r]s[l1]

如果 l = 1 l = 1 l=1,则 sum ( l , r ) = s [ r ] \text{sum}(l, r) = s[r] sum(l,r)=s[r]

二维前缀和是前缀和思想的扩展,适用于矩阵。对于一个 n × m n \times m n×m 的矩阵 a a a,我们定义一个二维前缀和矩阵 s s s,其中 s [ i ] [ j ] s[i][j] s[i][j] 表示从矩阵左上角 ( 1 , 1 ) (1, 1) (1,1) 到右下角 ( i , j ) (i, j) (i,j) 的所有元素的和:
s [ i ] [ j ] = ∑ x = 1 i ∑ y = 1 j a [ x ] [ y ] s[i][j] = \sum_{x=1}^{i} \sum_{y=1}^{j} a[x][y] s[i][j]=x=1iy=1ja[x][y]

通过二维前缀和矩阵 s s s,我们可以快速计算任意子矩阵 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 的和:
s ( x 1 , y 1 , x 2 , y 2 ) = s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] + s [ x 1 − 1 ] [ y 1 − 1 ] {s}(x_1, y_1, x_2, y_2) = s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] + s[x_1-1][y_1-1] s(x1,y1,x2,y2)=s[x2][y2]s[x11][y2]s[x2][y11]+s[x11][y11]


2 一维板子

原题链接:DP34 【模板】前缀和

给定一个长度为 n n n 的数组 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an。接下来有 q q q 次查询,每次查询有两个参数 l , r l, r l,r。对于每个询问,请输出 a l + a l + 1 + . . . + a r a_l + a_{l+1} + ... + a_r al+al+1+...+ar

输入描述:

第一行包含两个整数 n n n q q q,第二行包含 n n n 个整数,表示 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an。接下来 q q q 行,每行包含两个整数 l l l r r r

  • 1 ≤ n , q ≤ 1 0 5 1 \leq n, q \leq 10^5 1n,q105
  • − 1 0 9 ≤ a [ i ] ≤ 1 0 9 -10^9 \leq a[i] \leq 10^9 109a[i]109
  • 1 ≤ l ≤ r ≤ n 1 \leq l \leq r \leq n 1lrn

输出描述:
输出 q q q 行,每行代表一次查询的结果。

示例:
input:

3 2
1 2 4
1 2
2 3

output:

3
6
#include <iostream>
#include <vector>
using namespace std;#define endl '\n'
#define LL long longvector<LL> a(101010, 0);
vector<LL> s(101010, 0);int main()
{int n, q;cin >> n >> q;for (int i = 1; i <= n; i++) {cin >> a[i];s[i] = s[i - 1] + a[i];}while (q--) {int l, r;cin >> l >> r;cout << s[r] - s[l - 1] << endl;}return 0;
}

时间复杂度: 预处理前缀和数组的时间复杂度为 O ( n ) O(n) O(n),每次查询的时间复杂度为 O ( 1 ) O(1) O(1)


3 二维板子

原题链接:DP35 【模板】二维前缀和

给你一个 n n n m m m 列的矩阵 A A A,下标从1开始。接下来有 q q q 次查询,每次查询输入4个参数 x 1 x_1 x1, y 1 y_1 y1, x 2 x_2 x2, y 2 y_2 y2。请输出以 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 为左上角, ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 为右下角的子矩阵的和。

输入描述:
第一行包含三个整数 n n n, m m m, q q q

接下来 n n n 行,每行 m m m 个整数,代表矩阵的元素。

接下来 q q q 行,每行4个整数 x 1 x_1 x1, y 1 y_1 y1, x 2 x_2 x2, y 2 y_2 y2,分别代表这次查询的参数。

  • 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1n,m1000
  • 1 ≤ q ≤ 1 0 5 1 \leq q \leq 10^5 1q105
  • − 1 0 9 ≤ a [ i ] [ j ] ≤ 1 0 9 -10^9 \leq a[i][j] \leq 10^9 109a[i][j]109
  • 1 ≤ x 1 ≤ x 2 ≤ n 1 \leq x_1 \leq x_2 \leq n 1x1x2n
  • 1 ≤ y 1 ≤ y 2 ≤ m 1 \leq y_1 \leq y_2 \leq m 1y1y2m

输出描述:
输出 q q q 行,每行表示查询结果。

示例

输入:

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

输出:

12
26
#include <iostream>using namespace std;long long a[1010][1010];
long long s[1010][1010];int main()
{int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];}}int x1, x2, y1, y2;while (q--) {cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl;}return 0;
}

习题1:724.寻找数组中心下标 - e

724.寻找数组的中心下标 - easy

#include <iostream>
#include <vector>
using namespace std;/*
https://leetcode.cn/problems/find-pivot-index/description/
正常思路应该是:
2 * left_sum = sumclass Solution {
public:int pivotIndex(vector<int>& nums) {int sum = reduce(nums.begin(), nums.end());int left = 0;for (int i = 0; i < nums.size(); i++) {if (2 * left  == sum - nums[i]) {return i;}left += nums[i];}return -1;}
};*/class Solution {
public:int pivotIndex(vector<int>& nums){int n = nums.size();if (n == 0)return -1;// 前缀和数组,dp1[i] 表示 nums[0] 到 nums[i-1] 的和vector<int> dp1(n + 1, 0); // 后缀和数组,dp2[i] 表示 nums[i+1] 到 nums[n-1] 的和vector<int> dp2(n + 1, 0); for (int i = 1; i <= n; ++i) {dp1[i] = dp1[i - 1] + nums[i - 1];}for (int i = n - 1; i >= 0; --i) {dp2[i] = dp2[i + 1] + nums[i];}for (int i = 0; i < n; ++i) {if (dp1[i] == dp2[i + 1]) {return i;}}return -1;}
};int main()
{vector<int> nums = { 1, 7, 3, 6, 5, 6 };Solution sol;int ans = sol.pivotIndex(nums);cout << ans << endl;
}

习题2:303.区域和检索数组不可变 - e

303. 区域和检索 - 数组不可变 - easy

// https://leetcode.cn/problems/range-sum-query-immutable/
#include <iostream>
#include <vector>
using namespace std;
class NumArray {vector<int> s;
public:NumArray(vector<int>& nums){s.resize(nums.size() + 1);for (int i = 0; i < nums.size(); i++) {s[i + 1] = s[i] + nums[i];}}int sumRange(int left, int right){return s[right + 1] - s[left];}
};

习题3:238.除自身以外数组的乘积 - m

238. 除自身以外数组的乘积 - m

/* https://leetcode.cn/problems/product-of-array-except-self/description/ */#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums){int n = nums.size();vector<int> ans(n, 1);for (int i = 1; i < n; i++)ans[i] = ans[i - 1] * nums[i - 1];int suffix = 1;for (int i = n - 1; i >= 0; i--) {ans[i] = ans[i] * suffix;suffix *= nums[i];}return ans;}
};int main()
{vector<int> nums1 = { 1, 2, 3, 4 };Solution sol;vector<int> result1 = sol.productExceptSelf(nums1);for (int num : result1) {cout << num << " ";}cout << endl;
}/*class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> pre(n, 1);for (int i = 1; i < n; i++) {pre[i] = pre[i - 1] * nums[i - 1];}vector<int> suf(n, 1);for (int i = n - 2; i >= 0; i--) {suf[i] = suf[i + 1] * nums[i + 1];}vector<int> ans(n);for (int i = 0; i < n; i++) {ans[i] = pre[i] * suf[i];}return ans;}
};*/

习题4:

在这里插入图片描述

相关文章:

前缀和相关题目记录(未完待续...)

1 前缀和 一维前缀和是指对于一个数组 a a a&#xff0c;我们定义一个新的数组 s s s&#xff0c;其中每个元素 s [ i ] s[i] s[i] 表示从数组开头到第 i i i 个元素的累加和&#xff1a; s [ i ] a [ 1 ] a [ 2 ] ⋯ a [ i ] ∑ j 1 i a [ j ] s[i] a[1] a[2] \…...

Https解决了Http的哪些问题

部分内容来源&#xff1a;小林coding 详细解析 Http的风险 HTTP 由于是明文传输&#xff0c;所以安全上存在以下三个风险&#xff1a; 1.窃听风险 比如通信链路上可以获取通信内容&#xff0c;用户号容易没。 2.篡改风险 比如强制植入垃圾广告&#xff0c;视觉污染&#…...

OpenCV给图像添加噪声

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 如果你已经有了一张干净的图像&#xff0c;并希望通过编程方式向其添加噪声&#xff0c;可以使用 OpenCV 来实现这一点。以下是一个简单的例子&a…...

湖北中医药大学谱度众合(武汉)生命科技有限公司研究生工作站揭牌

2025年2月11日&#xff0c;湖北中医药大学&谱度众合&#xff08;武汉&#xff09;生命科技有限公司研究生工作站揭牌仪式在武汉生物技术研究院一楼101会议室举行&#xff0c;湖北中医药大学研究生院院长刘娅教授、基础医学院院长孔明望教授、基础医学院赵敏教授、基础医学院…...

欢乐力扣:快乐数

文章目录 1、题目描述2、思路1代码 1、题目描述 快乐数。  编写一个算法来判断一个数 n 是不是快乐数。  快乐数定义为&#xff1a;对于一个正整数&#xff0c;每次不断将其转化成 每位数字的平方和。 判断是否最终和会为1&#xff0c;是1就是快乐数&#xff0c;否则不是。 …...

【聊天室后端服务器开发】功能设计-框架与微服务

服务器功能设计 微服务思想应用 微服务架构 主要组成分析 客户端 客户端通过 HTTP 协议与网关进行交互&#xff0c;进行操作如用户注册、好友申请等客户端只需要知道网关的地址&#xff0c;无需关心后端服务的具体实现 网关 作为系统的统一入口&#xff0c;网关负责接收客…...

国标28181协议在智联视频超融合平台中的接入方法

一. 国标28181介绍 国标 28181 协议全称是《安全防范视频监控联网系统信息传输、交换、控制技术要求》&#xff0c;是国内视频行业最重要的国家标准&#xff0c;目前有三个版本&#xff1a; 2011 年&#xff1a;推出 GB/T 28181-2011 版本&#xff0c;为安防行业的前端设备、平…...

让网页“浪“起来:打造会呼吸的波浪背景

每次打开那些让人眼前一亮的网页时&#xff0c;你是否有注意到那些看似随波逐流的动态背景&#xff1f;今天咱们不聊高深的技术&#xff0c;就用最朴素的CSS&#xff0c;来解锁这个让页面瞬间鲜活的秘籍。无需JavaScript&#xff0c;不用复杂框架&#xff0c;准备好一杯咖啡&am…...

linux-多进程基础(1) 程序、进程、多道程序、并发与并行、进程相关命令,fork

程序是什么 程序是包含一系列信息的文件。这些信息描述了如何在运行时创建一个进程&#xff0c;包含二进制格式标识、机器语言指令、程序入口地址、数据、符号表及重定位表、共享库信息及其他信息 二进制格式标识&#xff0c;每个程序包含了描述可执行文件的元信息(是否可读之…...

美颜相机1.0

项目开发步骤 1 界面开发 美颜相机界面构成&#xff1a; 标题 尺寸 关闭方式 位置 可视化 2 创建主函数调用界面方法 3 添加两个面板 一个是按钮面板一个是图片面板 用JPanel 4 添加按钮到按钮面吧【注意&#xff1a;此时要用初始化按钮面板的方法initBtnPanel 并且将按钮添…...

Docker内存芭蕾:优雅调整容器内存的极限艺术

title: “&#x1f4be; Docker内存芭蕾&#xff1a;优雅调整容器内存的极限艺术” author: “Cjs” date: “2025-2-23” emoji: “&#x1fa70;&#x1f4a5;&#x1f4ca;” 当你的容器变成内存吸血鬼时… &#x1f680; 完美内存编排示范 &#x1f4dc; 智能内存管家脚本…...

gitlab初次登录为什么登不上去

今天又写了一次gitlab安装后&#xff0c;第一次登录的问题。 gitlab工作笔记_gitlab默认用户名密码-CSDN博客 因为又掉这个坑里了。 # 为什么第一次登录这么难&#xff1f; 第一是因为gitlab启动的时间很长&#xff0c;有时候以为装错了。 第二是初始密码&#xff0c;如果…...

单链表相关操作(基于C语言)

文章目录 单链表定义版本一(可自己选择是否含头节点)创建单链表打印单链表对单链表进行冒泡排序删除单链表中值为key的节点求单链表表长在单链表位序为i的位置插入新元素e 单链表定义 typedef struct node {int data;struct node* next; }LinkNode,*LinkList;版本一(可自己选择…...

SPRING10_SPRING的生命周期流程图

经过前面使用三大后置处理器BeanPostProcessor、BeanFactoryPostProcessor、InitializingBean对创建Bean流程中的干扰,梳理出SPRING的生命周期流程图如下...

从零到一学习c++(基础篇--筑基期十一-类)

从零到一学习C&#xff08;基础篇&#xff09; 作者&#xff1a;羡鱼肘子 温馨提示1&#xff1a;本篇是记录我的学习经历&#xff0c;会有不少片面的认知&#xff0c;万分期待您的指正。 温馨提示2&#xff1a;本篇会尽量用更加通俗的语言介绍c的基础&#xff0c;用通俗的语言去…...

Java String 类

Java String 类常用方法详解 在 Java 编程里&#xff0c;字符串操作十分常见&#xff0c;而 String 类作为 Java 标准库的核心类&#xff0c;用于表示不可变的字符序列。任何对字符串的修改操作都会返回一个新的字符串对象&#xff0c;不会改变原始字符串。本文将详细介绍 Str…...

P8665 [蓝桥杯 2018 省 A] 航班时间

P8665 [蓝桥杯 2018 省 A] 航班时间 题目代码分析 题目 代码 #include <iostream> #include <vector> #include <string> #include <algorithm> #include <math.h> #include <queue>#include <cctype> using namespace std; int t;…...

Vue3项目与pnpm使用教程

文章目录 Vue3项目与pnpm使用教程一、pnpm简介二、安装pnpm三、创建Vue3项目四、运行Vue3项目五、管理项目依赖六、配置pnpm七、使用pnpm的额外功能八、总结 Vue3项目与pnpm使用教程 一、pnpm简介 pnpm是一个高性能的Node.js包管理工具&#xff0c;相较于npm和yarn&#xff0…...

C++初阶——简单实现list

目录 1、前言 2、List.h 3、Test.cpp 1、前言 1. 简单实现std::list&#xff0c;重点&#xff1a;迭代器&#xff0c;类模板&#xff0c;运算符重载。 2. 并不是&#xff0c;所有的类&#xff0c;都需要深拷贝&#xff0c;像迭代器类模板&#xff0c;只是用别的类的资源&am…...

C/C++后端开发面经

字节跳动 客户端开发 实习 一面(50min) 自我介绍是否愿意转语言,是否只愿意搞后端选一个项目来详细谈谈HTTP和HTTPS有什么区别?谈一下HTTPS加密的具体过程&#xff1a; 非对称加密 对称加密 证书认证的方式 非对称加密是为了保证对称密钥的安全性。 对称…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...