数据结构之树状数组_第1页
数据结构之树状数组_第2页
数据结构之树状数组_第3页
数据结构之树状数组_第4页
数据结构之树状数组_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

树状数组,原数组是a，c是a的树状数组,可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5C8=a1+a2+a3+a4+a5+a6+a7+a8C2n=a1+a2+.+a2n,树状数组,对于序列a，我们设一个数组CCi=ai2k+1+aik为i在二进制下末尾0的个数C即为a的树状数组如何求k？,2k=xn+=lowbit(n);,树状数组,5、求和当要查询a1,a2.an的元素之和时,需要累加c数组中的q1,q2,q3.等一系列元素其中q1=n,q(i+1)=qi-lowbit(qi)所以计算a1+a2+.an可以实现为:intSum(intn)intresult=0;while(n!=0)result+=cn;n-=lowbit(n);returnresult;,树状数组,为什么是效率是log(n)的呢？以下给出证明：n=nlowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。换句话说:若需改变ai，则ci、ci+lowbit(i)、ci+lowbit(i)+lowbit(i+lowbit(i)就是需要改变的c数组中的元素。若需查询si，则ci、ci-lowbit(i)、ci-lowbit(i)-lowbit(i-lowbit(i)就是需要累加的c数组中的元素。6、与线段树的比较树状数组是一个可以很高效的进行区间统计的数据结构。在思想上类似于线段树，比线段树节省空间，编程复杂度比线段树低，但适用范围比线段树小。,线段树,树状数组,7、扩展-二维树状数组一维树状数组很容易扩展到二维，二维树状数组如下所示：Cxy=sum(Aij)其中，x-lowbitx+1=i=x且y-lowbity+1=j=y,树状数组（例）HDU1166,#include#include#include#includeusingnamespacestd;#defineN50005intn;intaN,cN;intlowbit(intx)return(x,intmain()intcas=0;intt,w,u,v;ch
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论