最新要闻
- 可怜的欧美!RTX 3070上市两年半 终于破发|今头条
- 环球头条:雷蛇噬魂鲨极速版耳机发布:50mm驱动单元、30小时续航
- 别只会“王者峡谷五日游” 这几款游戏才是假期最佳解
- 每日关注!4月新能源销量:比亚迪、埃安、理想全线杀疯
- 全球要闻:巨亏236亿元!三星内存、闪存要减产25%
- 天天热头条丨“天空之城”游人如织
- 世界观点:4年来首次下滑 AMD发布Q1季度财报:锐龙处理器成重灾区
- 五菱缤果营销比亚迪海豚话术曝光:颜值高、空间大
- 【速看料】五一后机票价格暴跌 飞三亚从2800降到280元 专家表态:很正常
- 联合国秘书长:呼吁以色列停止行政拘留的做法|全球观焦点
- 世界今热点:徊的拼音_徊怎么组词
- 流媒体时代谋生艰难!好莱坞编剧15年来将首次罢工
- 为何插电混动车主爱在外充电 理想高管分析:薅羊毛感觉爽
- 当前资讯!司机等红绿灯时看手机被罚200扣3分 车是静止状态:网友吵翻 但事实没错
- NV一代神卡卷土重来!Steam新报告:RTX 40降价仍没存在感_当前热议
- 五一想在户外看电影、选购投影仪一定要注意这几点
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
每日热文:前缀和
前缀和
一、介绍
前缀,顾名思义就是一个东西前面的点缀...(bushi
其实打比方来说就是:假如有一字符串ABCD,那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组,对于给定的数组a=[1,2,3,4],他的前 i 项和sum[i]就表示数组中a[0]~a[i]的和,具体为:sum[0]=a[0]sum[1]=a[0]+a[1]......sum[i]=sum[0]+sum[1]+...+sum[i];
二、定义
定义:前缀和是指某一序列的前 n 项和。
(资料图片仅供参考)
基于前缀和的使用,我们一般把前缀和分为一维前缀和和二维前缀和。
三、一维前缀和
定义
基于一维数组的前缀和就是原数组前n个元素的和。
const int N = 10010; int a[N]; //原数组a[]int s[N]; //前缀和数组s[] //根据定义 一维前缀和s[i]s[i] = a[1] + a[2] + a[3] +...+ a[i]; //举例 设i=3 根据上式可得s[3] = a[1] + a[2] + a[3]; //根据上面举例,可以再一步写成s[i] = s[i-1] + a[i];
需要注意的一点是:数组的下标都是从 1 开始的!!!
作用
主要作用是可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。
//例如求a[3]+...+a[10]之间的和,我们可以利用前缀和迅速求出: a[3]+...+a[10]= (a[1]+a[2]+a[3]...+a[10]) - (a[1]+a[2])= s[10] - s[2] //根据上面举例,我们可以推导出求某一区间[l,r]内的和的公式 a[l]+a[l+1]+...+a[r-1]+a[r] = s[r] - s[l-1];
方法
一维数组求前缀和方法
int a[100],s[100];for(int i = 1; i<= 99; i++){ scanf("%d",&a[i]);}for(int i = 1; i<= 99; i++){ s[i] = s[i-1]+a[i];}
实战演练!!!
「模板」前缀和
输入n个数,给出m个询问,询问区间[x,y]的和。
输入
第一行为n和m,1<=n,m<=100000
接下来一行为n个数,范围在0~100000之间
接下来m行,每行两个数x,y,输出第x个数到第y个数之间所有数的和。保证x<=y
输出
m个输出
样例输入
5 31 2 0 7 61 32 24 5
样例输出
3213
代码:
#include using namespace std;int n,m;long long a[100010],b[100010];//见注释1int main(){cin >> n >> m;for(int i=1; i<=n;i++){cin >> a[i];}b[0]=0;for(int i=1;i<=n;i++){b[i]=b[i-1]+a[i];}while(m--){int l,r;cin >> l >> r;cout << b[r] - b[l-1] << "\n";}return 0;}
注释①:测试范围大
四、二维前缀和
定义
基于二维数组的前缀和,它是指一个前 i 行和前 j 列的子矩阵的和
const int N =100010;int a[N][N] //原二维数组int s[N][N] //二维前缀和数组 //根据定义可得s[i][j] = a[1][1] + a[1][2] + ... + a[1][j]+ a[2][1] + 1[2][2] + ... + 1[2][j]+ a[3][1] + ... + ... + a[3][j]+ + + .... .... + + a[i][1] + ... + ... + a[i][j]
作用
主要作用是可以在是可以在O(1)情况下求出任何子矩阵的和
图解:
在这个矩阵(二维数组)中,我们要求上图中紫色区域的和,现在我们已经预处理出了所有点的前缀和,现在给定两个点\((x1,y1)\),\((x2,y2)\),我们需要求的是以这两个点连线为对角线的一个子矩阵的数值之和。首先我们可以把\(s[x2][y2]\)求出来,它代表整个大矩形的前缀和,然后我们分别减去它右边多出来的一块的前缀和和上边多出来一块的前缀和,但是需要注意下边的左上角被减了两次,所以我们需要加回来一次。故对于一次的查询是\(s[i][j]\)应该等于\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\)。
- 所求子矩阵和=\(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]\);
方法
二维数组求前缀和方法
const int N = 10010;int a[N][N],s[N][N]//n,m为键盘输入for(int i = 1; i <= n; i++){ for(int j = 1;j <= m; j++) { scanf("%d",&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]; }}
具体代码!!!
#include const int N = 1010;int n,m,q;int a[N][N],s[N][N]; int main(){ scanf("%d%d%d",&n,&m,&q); for(int i = 1; i <= n; i++) { for(int j = 1;j <= m; j++) { scanf("%d",&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]; } } while(q--) { int x1,y1,x2,y2,re; scanf("%d%d%d%d",&x1,&y2,&x2,&y2); re = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]; printf("%d\n",re); }}
关键词:
每日热文:前缀和
可怜的欧美!RTX 3070上市两年半 终于破发|今头条
环球头条:雷蛇噬魂鲨极速版耳机发布:50mm驱动单元、30小时续航
别只会“王者峡谷五日游” 这几款游戏才是假期最佳解
每日关注!4月新能源销量:比亚迪、埃安、理想全线杀疯
全球要闻:巨亏236亿元!三星内存、闪存要减产25%
天天热头条丨“天空之城”游人如织
学系统集成项目管理工程师(中项)系列16b_风险管理(下)
世界观点:4年来首次下滑 AMD发布Q1季度财报:锐龙处理器成重灾区
五菱缤果营销比亚迪海豚话术曝光:颜值高、空间大
【速看料】五一后机票价格暴跌 飞三亚从2800降到280元 专家表态:很正常
联合国秘书长:呼吁以色列停止行政拘留的做法|全球观焦点
python图像处理库
Java读取数据库表
世界今热点:徊的拼音_徊怎么组词
流媒体时代谋生艰难!好莱坞编剧15年来将首次罢工
为何插电混动车主爱在外充电 理想高管分析:薅羊毛感觉爽
当前资讯!司机等红绿灯时看手机被罚200扣3分 车是静止状态:网友吵翻 但事实没错
NV一代神卡卷土重来!Steam新报告:RTX 40降价仍没存在感_当前热议
五一想在户外看电影、选购投影仪一定要注意这几点
浙商证券研究所所长助理陈杭离职:否认网传800万年薪,专心处理舆论_世界热资讯
81.数组 全球热门
Win11“颠覆性”功能被遗弃:失效三个月仍被微软无视
嘴硬还是明智?丰田高管:电动汽车技术不成熟、混动才实用
同花顺ai机构活跃度指标公式源码_活跃度100
Android-图片压缩(二)-纯干货
C# 常量 结构体 委托 热门看点
喝的二五八万是什么意思_二五八万是什么意思
性能达SteamDeck两倍!华硕ROG Ally掌机先行开箱来了
奇葩!插队发飙者称是换队 网友吐槽发飙发泼有理:景区称仍算插队
天天热议:手机就能跑!开源AI机器人MLC LLM发布:无需联网
喜欢玩手机 那就活该单身
沃尔沃首款全电动汽车现已准备好接触其首批英国客户
降价伤人伤己?特斯拉国内外突然涨价背后:实为去库存|每日短讯
ChatGPT导致信息泄露后:三星将开发内部AI工具
女子淄博吃烧烤排不上队被投喂饱 山东太热情:人民日报点赞
11.迷宫问题(BFS 储存路径)
哈弗的新款Boxy SUV由前路虎设计师设计|世界球精选
韩国大学生吃掉天价香蕉艺术品 称是行为艺术!原作者回应了 每日速读
焦点快报!最高热效率达44%:五菱柳机自研高热效发动机点火成功
私拆承重墙高楼已加固 居民称胆真大:多层裂纹被掩盖 还敢住吗
坏账损失核算方法有_坏账损失核算方法 世界即时看
卖不动很无奈?NVIDIA对RTX 4090官降:今年第三次了
华为重申保持创新:1年1615亿研发费下14nm以上EDA国产化 5G必要专利全球第一_全球观热点
appuploader iOS 应用自动发布
苹果酸酶_关于苹果酸酶的简介
Windows 12这般模样?概念设计出炉:任务栏/开始菜单无比舒服 天天头条
21 文件六大基本操作|焦点速读
Tomcat7安装基于jdk 1.7环境
全球资讯:STM32_5(中断)
ASML吓坏?俄罗斯放狠话加快自研光刻机 能产7nm芯片:合作伙伴敲定
画面瘆人!印度机场从一女子包中搜出22种蛇 环球百事通
《最终幻想16》召唤兽概念图曝光!极具设计感 世界热闻
显存容量很重要!RTX 3060 8GB魔改12GB显存后:性能提升22%-全球球精选
全球播报:长城魏玛奇朵dht-phev特调版外观设计精致,线条流畅
业主拆承重墙 裂缝已蔓延到21层行为被称谋杀:律师回应公共安全罪可刑拘-当前短讯
被指插队发飙当事人回应原委上热搜 是排队平移非插队:自己被冤枉 网友看醉
世界最新:物业公司在小区建简易摊位 合同到期 业主能不能收回?
哈希表与布隆过滤器
全球观热点:好客山东名不虚传!淄博0.85米志愿者喝着奶帮看行李
爱买不买?三星等国外大厂减产倒逼SSD等存储涨价 国产厂商不怕|焦点资讯
当前资讯!素质堪忧?垃圾站现1000万日元 日本12人前去冒领:最终结果意外
孔雀为躲游客拔毛被滑车碾压:为珍贵白孔雀!景区回应_全球速看
【世界报资讯】五一“赛程近半” 文娱及旅游等消费数据有多强劲?
gcc/g++编译 全球最新
全球百事通!家电行业周报:三大白电4月空冰洗排产数据较好
每日简讯:提前十一天!《塞尔达传说:王国之泪》意外偷跑:模拟器可玩
终于像是“次世代”了:微软为Xbox开发新版UI
高质量发展调研行丨产业集群提速 项目建设正酣-天天快资讯
五一返程注意!暴雨大暴雨要来了:华东、华中将现今年来最强降雨_环球快讯
世界微资讯!特斯拉差点破产:马斯克入选瑞典“失败博物馆”
曝小鹏“自动驾驶”避让大车险冲出高架 客服回应:会反馈核实|世界播资讯
时讯:失业潮或在路上!IBM计划用AI取代7800个岗位
环球观焦点:5月24开播!美版《西游ABC》来了:杨紫琼演观音 吴彦祖演美猴王
天天热头条丨傅欢俱乐部赛事达成200次出场,中超175场,中甲25场
频频把辅助驾驶当成自动驾驶:一嘴硬的理想车主撞了-全球热门
云南母鸡山服务区冲厕出现红水吓跑小孩:工作人员释疑 长见识 全球即时
对标苹果!微软自研Arm芯片在路上了|天天播报
靠增程抢的充电桩 凭什么让给纯电? 当前速讯
环球观察:学系统集成项目管理工程师(中项)系列16a_风险管理(上)
今亮点!AI组建社交鬼城 所有人类禁止入内:上万AI自主聊天!
加快IPv4退网:我国IPv6从能用到好用了_当前速看
靠增程抢的充电桩 凭什么让给纯电?
苹果版“余额宝”开局迅猛!Apple Card四天吸金69亿元_天天报资讯
全球球精选!刘亦菲国籍能改回来吗 刘亦菲国籍
【经验分享】使用Windows自带Xbox显示游戏帧率
美国4月ISM制造业环比上升但连续六个月萎缩,Markit制造业重回扩张
23年4月新能源汽车品牌销量排名来了 埃安、理想杀疯了|焦点资讯
超越《长空之王》!电影《人生路不熟》成劳动节单日票房冠军
【全球新视野】特斯拉又“失控” 车头撞没:这次不是单踏板的祸 别克变道所致网友称可怜
国内票房破4亿!《长空之王》国外口碑解禁:老外狂赞 歼20等精彩
孙殿义_环球新资讯
热资讯!孙楼村
算法3:质数的个数-全球观察
【世界报资讯】扛起农业大市担当 打造新时代鱼米之乡实践样板
视点!小米汽车可期!网友在厦门4S店偶遇卢伟冰
男子路边尝大爷樱桃没买被收2元直呼憋气 主动让尝:网友吐槽坑
全球聚焦:找段错误找了一个小时,纪念一下
环球今热点:2023-05-01:给你一个整数 n , 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]
20 文件系统的格式化操作_世界聚看点