数组差分与前缀和
2021/12/25 23:10:50
本文主要是介绍数组差分与前缀和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数组差分与前缀和
一、差分
差分就是把数组表现成初始数和一堆差的形式。
例:7 9 2 1 4 5
差分形式:7 2 -7 -1 3 1
这时可以发现:
\(7=7\)
\(9=7+2\)
\(2=7+2+(-7)\)
\(1=7+2+(-7)+(-1)\)
\(4=7+2+(-7)+(-1)+3\)
\(5=7+2+(-7)+(-1)+3+1\)
当把数组转换成差分形式后,就可以很轻松的进行区间修改
如果想要把\(a[x]-a[y]\)同时加上\(delta\),只需将\(d[x]+Δ,d[y+1]-Δ\),这时再
就可以得出修改后的\(a[n]\)了。
差分的优点在于可以通过修改差分数组起始和结尾来迅速进行区间修改。
二、前缀和
前缀和本身与差分差不多。
例:7 9 2 1 4 5
前缀和形式:7 16 18 19 23 28
通过观察,可以发现\(a[i]=d[i+1]-d[i]\)
那么\(d[x]-d[y-1]\)就可以求出\([a[x],a[y]]\)这个区间的和,从而实现区间求和的目的。
前缀和的优点在于可以通过将数组两项做差方便的进行区间求和。
这篇关于数组差分与前缀和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南