- 1、本文档共87页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
树状数组及其应用 引例 【题目描述】 输入一个数列A1,A2….An(1=N=100000),在数列上进行M(1=M=100000)次操作,操作有以下两种: 格式为C I X,其中C为字符“C”,I和X(1=I=N,|X|=10000)都是整数,表示把把a[I]改为X 格式为Q L R,其中Q为字符“Q”,L和R表示询问区间为[L,R](1=L=R=N),表示询问A[L]+…+A[R]的值。 【输入】 第一行输入N(1=N=100000),表述数列的长度,接下来N行,每行一个整数(绝对值不超过10000)依次输入每个数;接下来输入一个整数M(1=M=100000),表示操作数量,接下来M行,每行为C I X或者Q L R。 【输出】 对于每个Q L R 的操作输出答案。 如果直接用数组模拟,那么修改是O(1),查询是O(n),如果维护另一个数组b[i],表示a[1]到a[i]的和,那么修改是O(n),查询时O(1)。 一个程序的时间复杂度取决于其中最大的时间复杂度。 树状数组的目的就是平摊修改和查询的时间,使复杂度由O(n)降到O(lgn)。 树状数组是一种数据结构,这种结构能让我们的程序变得高效,数据结构大多数时候是为了优化算法而用的。 树状数组对于原数组a维护另一个数组c,c[i]表示sum(a[j]),i-lowbit(i)+1=j=i,其中lowbit(i)表示取出i二进制表示中最右边的1。 例如lowbit(6)=lowbit(110)2=(10)2=2 所以 c[6]=a[5]+a[6]; lowbit(4)=lowbit(100)2=(100)2=4 c[4]=a[1]+a[2]+a[3]+a[4] lowbit[5]=lowbit(101) 2 =(1) 2=1; c[5]=a[5] 其比较简单的算法为 lowbit(i)=i (-i) 或i (i ^ (i-1)) 结论 1、节点i的父亲节点为i+lowbit(i) 2、节点i的最近不相交前驱为i-lowbit(i) 3、若需改变a[i],则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限,就是需要改变的c数组中的元素。 4、若需查询s[i],则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。 5、以上的修改和查询都是log2(n)级别的。 Procedure add(k,delt); Begin while k=limit do begin C[k]:=C[k]+delta; k:=k+lowbit(k); End; End; Function getsum(k:integer):integer; Var t:integer; Begin t:=0; while k0 do begin t:=t+c[k]; k:=k-lowbit(k); end; getsum:=t; End; 在实际应用中,通常不需要保存原数组a,只保存数组c即可。因此,树状数组几乎不需要附加空间。 通过上面的学习可以看出:树状数组所能支持的操作是修改点值、查询区间和。 与线段树和其他数据结构相比,树状数组代码简单,常数小,在其能解决范围内或经过转化使用树状数组,可以极大的降低编程复杂度,使代码清晰,简洁 例题、Stars(ural 1028) 题目大意 平面中有N个点,对于 每个点(x,y),要求输 出在其左下方(包括正 左正下)点的个数。 N=100000; x,y=maxlongint 枚举? 代码简单,时间复杂度达到O(n2) 有没有代码简单、时间复杂度低的方法? 此题有效的算法很多,树状数组可以简洁快速的解决此问题。 如何构建树状数组? 如何处理巨大的(x,y)? 如何处理“左下方”? 首先,离散化y坐标,然后按x坐标从小到大 排序,x相同则y坐标由小到大,从左到右扫描每个点,这样可以保证已经插入树状数组的点都在左侧或正下侧。 我们只需寻找有 多少点位于当前点下 方,很容易想到树状 数组。处理完当前点 后,将其按y坐标插入 树状数组,即让a[y]加1 此题是树状数组的经典应用 首先离散化坐标使数据范围减小,为使用树状数组创造了条件 按横坐标排序,使得原题中“左下方”两个条件限制转化为“下方”这一单一限制 可以轻松运用树状数组解决 现在,我们将树状数组推广到二维 先看一道神奇的题目 2、Superbrother打鼹鼠(vijos 1512)
您可能关注的文档
- 成都理工大学GPS课程本科试题库第一章绪论讲述.docx
- 成都河心岛项目精简版介绍讲述.ppt
- 数据中心的服务器虚拟化与运维管理解决方案_V1.0解读.docx
- 数据中心机房管理制度解读.doc
- 成都理工大学GPS课程本科试题库第二章坐标系统和时间系统讲述.docx
- 中美对待赞美的不同之处详解.ppt
- 成都2016上半年房地产市场报告讲述.ppt
- 中级客车检车员详解.docx
- 染整工艺原理复习题(补充版)解读.doc
- 柔性版印刷工艺解读.ppt
- 2021-2022学年广东省广州市南沙中考物理押题卷含解析 .pdf
- 2022-2023学年全国初中九年级下化学人教版月考试卷(含答案解析)084135.pdf
- 2021年湘教版七年级地理(下册)期中试卷及答案 .pdf
- 2021年九级中考数学压轴题满分训练 –几何综合问题(圆的专题)(二.pdf
- 1.1 集合的概念及表示-【新教材】人教A版(2019)高中数学必修一同步讲义.pdf
- 2022-2023学年广东省中考物理原题试卷附解析 .pdf
- (好题)初中数学七年级数学下册第六单元《概率初步》测试题(包含答案解 .pdf
- 2019九年级历史下册教案第12课-亚非拉民族民主运动的高涨.pdf
- 2021-2022学年沪科版八年级物理第九章 浮力综合测评试题(含解析).pdf
- 2022年全国中考数学试题真题汇编 一元一次方程(二) .pdf
最近下载
- 五四制初中一年级中华优秀传统文化教学设计.pptx VIP
- 《微生物与健康》课件科学六年级上册.pptx
- 七年级上册生物学《生物体的结构层次》单元作业设计.docx
- 电子信息工程职业规划 (第二版).pptx VIP
- 党的二十届三中全会精神测试题300道(单选、多选、判断、填空).docx VIP
- 部编教材年级识字课教学.ppt VIP
- 贵州省贵阳市2024-2025学年高一上学期10月联合考试(一) 数学 PDF版含解析.pdf
- 基于Android的个人生活行为记录及习惯养成平台的设计与实现-毕业设计.doc
- 中国传媒大学-节目主持艺术基础(第二版)-课件.pptx
- 纤维增强复合材料在建筑工程结构加固中的应用(经济论文资料).doc
文档评论(0)