树状数组及其应用双语版解读.ppt

  1. 1、本文档共87页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 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)

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档