版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
树状数组
树状数组的运用首先我们得知道一个问题,那就是线段树得作用并不只是用来存储线段的,也可以存储点的值等等.对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组.而在时间上虽然是NlogN的复杂度,但是系数很大.实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.树状数组的运用那么是否有更好的解决方法呢?有!那就是树状数组!树状数组的运用先看一个例题:数列操作:给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.树状数组的运用如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上树状数组的运用用线段树可以这样解:若要维护的序列范围是0..5,先构造下面的一棵线段树:树状数组的运用可以看出,这棵树的构造用二分便可以实现.复杂度是2*N.每个结点用数组a来表示该结点所表示范围内的数据之和.修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值.对于询问的回答,可以直接查找i..j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0..i-1的值和0..j的值,两个值减一减就行了.后者的实际操作次数比前者小一些.这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.树状数组的运用用树状数组!!!然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.怎么办树状数组的运用下图中的C数组就是树状数组,a数组是原数组先自己研究一下这个东西树状数组的运用可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5……C8=a1+a2+a3+a4+a5+a6+a7+a8……C2^n=a1+a2+….+a2^n树状数组的运用对于序列a,我们设一个数组C定义C[i]=a[i–2^k+1]+…+a[i],k为i在二进制下末尾0的个数。K的计算可以这样:2^k=xand(xxor(x-1))以6为例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2树状数组的运用functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x–1));end;若要修改a[i]的值,则C数组的修改是:Procedurechange(k,delta:integer);Beginwhilek<=ndobeginC[k]:=C[k]+delta;k:=k+lowbit(k);End;End;树状数组的运用若要求I..j的元素和的值,则求出1..I-1的值和1..j的值.Functiongetsum(k:integer):integer;Vart:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;getsum:=t;End;树状数组的运用对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.优秀的算法!树状数组的运用密码机(浙江2003省赛)算法:树状数组或者线段树与上题相比,所有的加号变成了xor.由于xor满足交换律,结合律,所以可以和加法一样地做.又AxorA=0,Axor0=A.所以ADD和REMOVE是一样的操作.树状数组的运用Ural1028Star
天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。
如果一个星星的左下方(包含正左和正下)有k颗星星,就说这颗星星是k级的.比如,在下面的例图中,星星5是3级的(1,2,4在它左下)。
星星2,4是1级的。例图中有1个0级,2个1级,1个2级,1个3级的星。求出各个级别的星星的个数树状数组的运用算法有很多种,最实用的是树状数组先对X排序,然后就是查找每个坐标前面的坐标种Y比他小的又多少个.这需要树状数组.树状数组存储的是某一段范围内有多少个点.小结
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023年中高压及特殊性能玻璃钢管资金筹措计划书
- 习作:缩写故事 教学设计-2024-2025学年语文五年级上册统编版
- 安徽省怀远一中2025年高三(下)期末生物试题试卷含解析
- 安徽省滁州市定远县民族中学2025年高三5月二模考试生物试题试卷含解析
- 2025年自贡市重点中学高三下学期第四次模拟考试卷生物试题理试卷含解析
- 七年级生物上册 第3单元 生物圈中的绿色植物 第6章 绿色植物的光合作用和呼吸作用 6.2 植物光合作用的场所教案 苏教版
- 广东省德庆县莫村中学2015届九年级体育上学期第十周 第1课 篮球胸前传接球教案
- 八年级英语下册 Unit 1 What's the matter Section A第1课时(1a-2d)教案(新版)人教新目标版
- 2025年云南省楚雄州双柏县一中高三5月定时练习生物试题试卷含解析
- 2025年四川省绵阳巿三台中学高三月考试卷(三)生物试题含解析
- 旅游经济学(第2版)绪论
- 麻醉质控培训课件
- 急诊科医疗质量评估与改进
- 体育解说员合作合同样本
- IPv6地址规划及部署实施方案
- 5G网络安全防护关键技术研究
- 十佳歌手赛评分表
- 一 《展示国家工程 了解工匠贡献》(教学设计)-【中职专用】高二语文精讲课堂(高教版2023·职业模块)
- 身心灵疗愈行业前景分析
- 第5课+认识情绪+管理情绪【中职专用】《心理健康与职业生涯规划》(高教版2023基础模块)
- 小学三年级信息技术课件
评论
0/150
提交评论