统计的力量-线段树.ppt

《统计的力量-线段树.ppt》由会员分享，可在线阅读，更多相关《统计的力量-线段树.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、统计的力量-线段树 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2022年年12月月7日日清清华大学大学 张昆昆玮2*根据 D.E.Knuth 的分类方法计算机算法可以分为两类：*数值算法与非数值算法*其中的非数值算法包括：*索引*分类*统计*2022年年12月月7日日清清华大学大学 张昆昆玮3*大家都说：*常数很大？*不好写？*难调试？*想不到？*2022年年12月月7日日清清华大学大学 张昆昆玮4*POJ上的某题，时限很紧*大家都用树状数组，但是有人只会用线

2、段树呢？*而且我可以轻易改出一道不能用树状数组的题*在线段树一次次TLE后，有一个ID发帖抱怨*“下次写一个汇编版非非递归线段树，再超时？”*可是大家都知道，超时的代码已经2k了。*其实我写的就是线段树。很快，而且不到1k。2022年年12月月7日日清清华大学大学 张昆昆玮5*运行速度快*适应能力强*编写方便*结构简单*容易调试*关键在于灵活灵活实现*为什么在算法导论和黑书中都难见到其踪迹？2022年年12月月7日日清清华大学大学 张昆昆玮62022年年12月月7日日清清华大学大学 张昆昆玮7*计算几何在长期的发展中，诞生了许多实用的数据结构。*区间查询，穿刺查询都是计算几何解决的问题*作为特

3、例中的特例，线段树解决的问题是：*一维空间上的几何统计*高维推广（kd-tree&）可以进行正交查询*由于竞赛中涉及计算几何的内容有限，不展开2022年年12月月7日日清清华大学大学 张昆昆玮8*线段树把数轴分成区间来处理*如8,10),10,11),*实际上我们面对的往往是离散量*竞赛中出现的线段树往往因此退化为“点树”*即，最底层的线段只包含一个点：*如：8,9)中只有整点8而已*在之后的讨论中，我们不再区别“点树”与线段树*如果我给MM的第一印象不到80分的话是不是老老实实地早点罢手比较好？2022年年12月月7日日清清华大学大学 张昆昆玮92022年年12月月7日日清清华大学大学 张昆

4、昆玮10*0,4)0,2)012,4)231,4)?2022年年12月月7日日清清华大学大学 张昆昆玮11*1,4)in 0,4)*左边，1,2)in 0,2)*Get 1*Get 2,4)in 2,4)*虽然每次都有可能同时递归进入两棵子树，但每层实际上只访问了两个节点。为什么？*因为查询是连续的啊2022年年12月月7日日清清华大学大学 张昆昆玮12*ABC如果同一层有三个被访问，依次为A，B，C查询是连续的，有了A和C，就一定包括B在树中的兄弟那我直接用B的父亲来计算好了，为什么要用B？*功利点说，没啥用的东西咱不学2022年年12月月7日日清清华大学大学 张昆昆玮13*直接把原数组处理

5、成前缀和*For i=2 to n do*Ai+=Ai-1*Ans(a,b)=Aa-Ab-1区区区间和，用的着线段树？2022年年12月月7日日清清华大学大学 张昆昆玮142022年年12月月7日日清清华大学大学 张昆昆玮15*原因是区间和的性质非常好*满足区区间减法减法*区间减法什么的最讨厌了！后面再说！*不过直接前缀和不是万能的！*如果修改元素的话2022年年12月月7日日清清华大学大学 张昆昆玮16*数据数据结构构修改元素修改元素取前取前缀和和直接存储原数组O(1)O(n)直接存储前缀和O(n)O(1)线段树O(logn)O(logn)*这个问题，本来本来是仁者见仁，智者见智的啊但是我要

6、讲一点不那么“本来本来”的东西2022年年12月月7日日清清华大学大学 张昆昆玮172022年年12月月7日日清清华大学大学 张昆昆玮18*访问线段*如果要的是整条线段就直接返回*如果与左子线段相交就递归处理*如果与右子线段相交就递归处理*合并所得到的解*遗憾的是，这种朴素的方法并不是那么容易并不是那么容易实现*而且存在严重的效率问题（常数太大）*2022年年12月月7日日清清华大学大学 张昆昆玮19*工欲善其事，必先利其器。2022年年12月月7日日清清华大学大学 张昆昆玮202022年年12月月7日日清清华大学大学 张昆昆玮21*虽然可以设计出三叉，四叉，线段树*但是我们先从二叉二叉树开始

7、*登高必自迩，行远必自卑*多叉怎么办后面再讲（这还要讲？自己研究去）*为了不处理各种特殊情况，假设二叉树是满的！*不是满的？你的总区间是0,1000)？*你就当作0,1024)不就好了？2022年年12月月7日日清清华大学大学 张昆昆玮22*12453672022年年12月月7日日清清华大学大学 张昆昆玮23*N 的左儿子是 2N*N 的右儿子是 2N+1*N 的父亲是 N 1*不就是个堆存储么？不用讲了吧？2022年年12月月7日日清清华大学大学 张昆昆玮24*1 10100101111101112022年年12月月7日日清清华大学大学 张昆昆玮25*字母树！*存放的是100,101,110

8、,111四个串！*每个节点存的是以这个节点为前缀的所有节点和*例：1中存的是所有四个以1开头的和。*似乎从 100 到 111 就正好是原数组*貌似下标减 4 就行了？2022年年12月月7日日清清华大学大学 张昆昆玮26*我们可以直接找到一个数对应的叶子*不用自顶向下慢慢地找啊找*“直接加 4”多简单！*直接找到叶子？*无限遐想中*可以直接找到叶子？2022年年12月月7日日清清华大学大学 张昆昆玮272022年年12月月7日日清清华大学大学 张昆昆玮28*124895101136121371415(0,5)?2022年年12月月7日日清清华大学大学 张昆昆玮29*1248951011361

9、21371415(0,5)?2022年年12月月7日日清清华大学大学 张昆昆玮30*Func Query(s,t)/询问从s到t闭区间*s=s 1,t=t+1;/变为开区间*s+=M,t+=M;/找到叶子位置*While not(s xor t)=1)do*If(s and 1)=0)Answer+=Trees+1;*If(t and 1)=1)Answer+=Treet 1;*s=s 1,t=t 1;2022年年12月月7日日清清华大学大学 张昆昆玮31*for(s=s+M-1,t=t+M+1;st1;s=1,t=1)*if(s&1)Ans+=Ts1;*if(t&1)Ans+=Tt1;*20

10、22年年12月月7日日清清华大学大学 张昆昆玮32*在将闭区间转化成开区间的时候可能越界1*理论上能放 0,2N)的树*其实只能查询 1,2N-2 的范围*切记切记2022年年12月月7日日清清华大学大学 张昆昆玮33*如果需要查询 0 就整个向后平移一下*所有下标加一！*如果需要在0,1024)中查询1023结尾的区间？*慢！你的数据规模不是 1000 么？*如果真的要到1023，直接把总区间变成0,2048)*就是这么狠！2022年年12月月7日日清清华大学大学 张昆昆玮34*Func Change(n,NewValue)*n+=M;*Treen=NewValue;*While n 1 d

11、o*n=n 1;*Treen =Tree2n+Tree2n+1;2022年年12月月7日日清清华大学大学 张昆昆玮35*for(Tn+=M=V,n=1;n;n=1)*Tn=Tn+n+Tn+n+1;*没了？*没了。2022年年12月月7日日清清华大学大学 张昆昆玮36*仅使用了两倍原数组的空间*其中还完整地包括了原数组*构造容易:*For i=M-1 downto 1 do Ti=T2i+T2i+1;*太好写了！好理解！*自底向上，只访问一次，而且不一定访问到顶层*实践中非常快，与树状数组接近*为什么呢？后面再讲。2022年年12月月7日日清清华大学大学 张昆昆玮37*因为树状数组依赖于区间减法

12、*区间减法什么的，最讨厌了后面再讲，再讲*反正如果只问问前缀和，不问区间和的话*那我也可以只用一倍空间！2022年年12月月7日日清清华大学大学 张昆昆玮38*124895101136121371415(,5)?2022年年12月月7日日清清华大学大学 张昆昆玮39*124895101136121371415(,5)?2022年年12月月7日日清清华大学大学 张昆昆玮40*124895101136121371415(,5)?2022年年12月月7日日清清华大学大学 张昆昆玮41*1-No2-14-25-No3-No6-37-No2022年年12月月7日日清清华大学大学 张昆昆玮42*这不就和树

13、状数组一样了？*本来就应该一样。*回过头说，树状数组究竟是什么？*就是省掉一半空间后的线段树加上中序遍历*计算位置需要lowbit什么的*我们用的是先序遍历，符合人的思考习惯。但是，这个空间没必要省。费点空间能换来实现的绝对简单。2022年年12月月7日日清清华大学大学 张昆昆玮43*树状数组线段树2022年年12月月7日日清清华大学大学 张昆昆玮44*我之前用这种写法做过不少题*大家都说我的代码看不懂*我说这就是一个树状数组*写树状数组的人说没有lowbit*我说那就算是线段树吧*大家不相信非递归的线段树这么短*我：*懒惰即美德。2022年年12月月7日日清清华大学大学 张昆昆玮45*噩梦的

14、开始2022年年12月月7日日清清华大学大学 张昆昆玮462022年年12月月7日日清清华大学大学 张昆昆玮47*RMQ(Range Minimum Query)*区间最小值查询*线段树*支持区间修改：*某一区间的数值全部增加一个可正可负的数*暴力修改不灵了！2022年年12月月7日日清清华大学大学 张昆昆玮48*在线段树上的每个节点增加一个标记*表示这一区间被增加过多少*在自顶而下的递归过程中*如果看到标记，就更新当前节点的值*并将标记下传*嗯？又要自顶向下？2022年年12月月7日日清清华大学大学 张昆昆玮49*其实堆式存储也可以自顶向下访问*就是上下各走一次而已*但是我们有更好的办法（使

15、劲想想就知道了）*不再下不再下传标记，而是随用随查*在自底向上的查询过程中*每向上走一层，就按照对应的标记调整答案*仔细想想很有道理。我们愿意把尽可能多的信息存放在树的根部，所以下传标记做什么？*庄周梦蝶而已2022年年12月月7日日清清华大学大学 张昆昆玮502022年年12月月7日日清清华大学大学 张昆昆玮51*一根线段，支持区间染色。询问区间是否同色？*区间染色需要使用染色标记1表示红色，2表示蓝色，3绿色，0杂色*询问的时候就直接看标记嘛2022年年12月月7日日清清华大学大学 张昆昆玮52*2为红色，3为蓝色，1为杂色修改3为红色查询1，杂色？*永久化的永久化的标记就是就是值啊！啊！

16、值是自动维护的啊！*其实我们的修改算法在修改3的时候已经维护了1*自底向上顺便重算所有遇到的节点标记即可*If(Markx=0 and Mark2x=Mark2x+1)*Markx=Mark2x;2022年年12月月7日日清清华大学大学 张昆昆玮53*回到区间修改的RMQ*通俗地讲，标记就是一个相对的量*既然有了标记，值还有什么用？*或者说，如果值本身就是相对的，还需要标记？*如果我让所有的数都从零开始变化，那标记永久化之后，所有值都恒为零啊！*于是我们连值也不存了。永久化的标记就是值。2022年年12月月7日日清清华大学大学 张昆昆玮54*每个节点不存区间最大值Tn了存放Mn=Tn-Tn1*

17、让每一个节点的值都减除它父亲的值*区间修改就直接改Mn。*查询就是从要查的节点开始一直加到根。Tn=Mn+Mn1+M1;*遇到节点x，则 A=min(M2x,M2x+1)Mx+=A,M2x-=A,M2x+1-=A2022年年12月月7日日清清华大学大学 张昆昆玮55*Func Add_x(s,t,x)*for(s=s+M-1,t=t+M+1;st1;s=1,t=1)*if(s&1)Ts1+=x;*if(t&1)Tt1+=x;*A=min(Ts,Ts1),Ts-=A,Ts1-=A,Ts1+=A;*A=min(Tt,Tt1),Tt-=A,Tt1-=A,Tt1+=A;*2022年年12月月7日日清清

18、华大学大学 张昆昆玮56*Func Max(s,t)*for(s=s+M-1,t=t+M+1;st1;s=1,t=1)*LAns+=Ts,Rans+=Tt;*if(s&1)LAns=max(LAns,Ts1);*if(t&1)RAns=max(RAns,Tt1);*Ans=max(LAns,RAns);*while(s1)Ans+=Ts=1;2022年年12月月7日日清清华大学大学 张昆昆玮57*差分是化绝对为相对的重要手段*标记永久化后就是值，只不过这种值是相对的*计算答案时可以利用从节点到根部的信息2022年年12月月7日日清清华大学大学 张昆昆玮58*截至PPT制作时，大家用的线段树自顶

19、向下居多*在自顶向下的线段树中，标记往往不是永久化的*对于RMQ，需要下传标记*对于染色问题，需要下传并收集标记*思想与这里我的方法差不多，实现上差别较大*至少上下各访问一次，较慢*参见其他资料2022年年12月月7日日清清华大学大学 张昆昆玮59*线段树是连接原数组和前缀和的桥梁*桥梁两边同时取差分*前缀和与差分互为逆运算*因此线段树也是连接差分和原数组的桥梁*如果要支持区间修改，单点查询*无需使用标记，直接将原数组差分*用线段树维护差分数组的前缀和即可。讲了了2022年年12月月7日日清清华大学大学 张昆昆玮60*不借助标记，支持区间修改和区间求和（原创）*先差分后变成维护一个前缀和的前缀

20、和*别被吓到，前缀和的前缀和是什么*SS1=S1 =x1*SS2=S1+=2x1+x2*SS3=S1+S2+S3=3x1+2x2+x3 =4(x1+x2+x3)-(1x1+2x2+3x3)*多维护一个nxn的前缀和就行了。2022年年12月月7日日清清华大学大学 张昆昆玮61*最长上升“区间列”*在一个区间列中按顺序找出最多区间使得不重叠，单调增*如 1,3 2,4 4,5 答案是1,3+4,5*动态规划的可行决策是什么呢？如果要使上升列长度大于x，最后一个数最小是多少，记为fx*维护fx支持点查询和区间修改。2022年年12月月7日日清清华大学大学 张昆昆玮62*点查询：查询x处fx的值*区

21、间修改：x左边的所有超过K的值，变为K*把x的左右换一下（囧）*整个f-x就是单调减的*一个单调减的序列可以看作是由一个普通序列经过前缀min得到的！*前缀min的逆运算是什么呢？*我们并不关心2022年年12月月7日日清清华大学大学 张昆昆玮63*我们现在要维护的就是前缀min的逆运算后的原序列！*可是我们甚至不知道前缀min的逆运算是什么*不要紧，反正用不到。*点查询：查询x处fx的值直接返回维护序列的前缀min*区间修改：x左边的所有超过K的值，变为K把维护序列中的fx变为K*2022年年12月月7日日清清华大学大学 张昆昆玮64*不要迷恋哥，哥只是个传说2022年年12月月7日日清清华

22、大学大学 张昆昆玮652022年年12月月7日日清清华大学大学 张昆昆玮66*说了这么多，能使用线段树解决问题的关键：*区间加法，即区间的“性质”由子区间完全决定*包括但不仅限于求和，求最值，求染色状态*这里的“性质”有点像动态规划的状态表示*有时候，求的更多反而更容易*最简单的例子：求区间第二最值*如果实在不满足区间加法，就全完了2022年年12月月7日日清清华大学大学 张昆昆玮67*我们都知道线段树求区间平均值不难*那求一个区间中位数试试？*什么，还不难？*那你再求个众数？*2022年年12月月7日日清清华大学大学 张昆昆玮68*越来越难的原因很简单*知道两区间的中位数，就知道和区间的中位

23、数？*知道各自众数有什么用？*2022年年12月月7日日清清华大学大学 张昆昆玮69*给定一列数，反复求区间第k大数。*要求的更多反而更容易更容易*线段树的每个区间必须保留更多的信息！*每个区间中存下区间所有数的有序数组*通过归并完成区间加法2022年年12月月7日日清清华大学大学 张昆昆玮70*如果每做一次查询就归并若干个线段*复杂度就会达到O(n)*离散化！二分答案！*变为求：x是区间第几大数？*这可以分别二分查找若干线段得到。*总复杂度O(nlogn+Q*log2n)2022年年12月月7日日清清华大学大学 张昆昆玮71*如果有了区间减法*线段树就能如虎添翼*如“区间和”变成“前缀和”*

24、操作能简单不少*同时也是能够使用树状数组的条件*但这不是必需的（和区间加法比一比）*我说过后面要讲的嘛2022年年12月月7日日清清华大学大学 张昆昆玮722022年年12月月7日日清清华大学大学 张昆昆玮73*维护一个数据结构支持*整数插入*取最大*整数范围是065535好了2022年年12月月7日日清清华大学大学 张昆昆玮74*堆当然可以*但是刘汝佳老师的黑书上有大招！*“分段哈希”*分成若干段，存下“段里面有没有数”信息2022年年12月月7日日清清华大学大学 张昆昆玮75*0,65536)0,256)02552022年年12月月7日日清清华大学大学 张昆昆玮76*如果多来几层呢？*3层

25、？4层？*到每个节点下面都只有两个点为止！*我们得到了什么2022年年12月月7日日清清华大学大学 张昆昆玮77*0,4)0,2)012,4)232022年年12月月7日日清清华大学大学 张昆昆玮78*分段哈希线段树*不要折腾2022年年12月月7日日清清华大学大学 张昆昆玮792022年年12月月7日日清清华大学大学 张昆昆玮80*维护一个数据结构支持*整数插入*整数删除*取第k大的数（取最大最小什么的就不说了）*查询数的排名*查某数是否存在*允许元素重复（为了难一点）*整数范围是065535好了2022年年12月月7日日清清华大学大学 张昆昆玮81*平衡树么？线段树！*统计0,65536)

26、每个数的出现频率，记为fx*整数插入，fx+*整数删除，fx-*查询数的排名，求前缀和*取第k大的数（取最大最小什么的就不说了）给定前缀和，查找自顶向下，左边不够就向右走，否则向左。2022年年12月月7日日清清华大学大学 张昆昆玮82*实测得到线段树用来处理这类问题非常快*平衡树中最快的Size Balanced Tree用了4秒多*线段树不到半秒全部出解。*这还没有分别减去读入数据的时间。*线段树使用刚刚所讲的实现，*代码量极小，且调试非常简单。2022年年12月月7日日清清华大学大学 张昆昆玮83*离散化。*不能离散化？*呵呵后面再讲2022年年12月月7日日清清华大学大学 张昆昆玮84

27、*维护一个数据结构支持*字符串插入*字符串删除*取第k大的字符串（取最大最小什么的就不说了）*查询字符串的排名*查某字符串是否存在2022年年12月月7日日清清华大学大学 张昆昆玮85*这里的size域的维护方式*和线段树如出一辙！*排名的计算方法，和之前整数的线段树完全一样*如果把字符串看作26进制数*那字母树就是线段树？2022年年12月月7日日清清华大学大学 张昆昆玮86*字母树线段树2022年年12月月7日日清清华大学大学 张昆昆玮87*所有节点用指针记录儿子*空间随用随开*不是满二叉树，甚至不完全*自顶向下处理所有问题*线段树也可以这样*数据范围再大，能比26N还大？2022年年12

28、月月7日日清清华大学大学 张昆昆玮88*就是一棵三十二层高的线段树指针式存储，节点像字母树一样动态生成*支持插入删除选择等等*复杂度是O(NlogM)，M是最大的数*对于long int，M=32*实测用了一秒多*（还记得平衡树四秒多么？）*自顶向下，只算前缀和，也不难写2022年年12月月7日日清清华大学大学 张昆昆玮89*像压缩字母树一样，会节约大量空间代价：不好写了*删除一个数之后尝试回收已经分配的节点代价：略慢，不好写了*树高动态化初始树高是1，只能放0每一次如果要放的数太大，增加一个根根的左儿子是当前的根，右儿子空。这个还实用！*在天愿作比翼鸟，在地愿为连理枝2022年年12月月7日

29、日清清华大学大学 张昆昆玮902022年年12月月7日日清清华大学大学 张昆昆玮91*平衡树上很多信息可以像线段树一样维护*平衡树就是一个会旋转的动态线段树！*最简单的，比如size域2022年年12月月7日日清清华大学大学 张昆昆玮92*块状链表的伤心题，标准程序5k+*维护一个数列，支持：*区间增加一个数*区间删除*区间插入*区间求和*区间翻转2022年年12月月7日日清清华大学大学 张昆昆玮93*平衡树 splay 可以支持：*区间删除*区间插入*线段树可以支持*区间增加一个数*区间求和*把线段树的值放在平衡树的节点上2022年年12月月7日日清清华大学大学 张昆昆玮94*每个节点表示它

30、和子树的信息总和*平衡树旋转时更新线段树的域*哇，会动的线段树2022年年12月月7日日清清华大学大学 张昆昆玮95*既要区间修改又要区间求和使用自顶向下的标记下传即可*为了处理区间反转增设一个bool值表示当前节点左右子树已经互换*先把区间从树中splay出再处理*要同时更改所有节点的反转标记？不记录反转标记，记录反转标记的标记（！）2022年年12月月7日日清清华大学大学 张昆昆玮96*但是所有部分都是相对简单的！*一点点写，只是很多很多小题而已*关于线段树，我们讲的已经太多了2022年年12月月7日日清清华大学大学 张昆昆玮972022年年12月月7日日清清华大学大学 张昆昆玮98*K-

31、th number 的另一个方法*如果区间互不包含，将所有要求的区间排个序来算。*用平衡树或线段树存下当前区间中的数*然后向下一个区间移动*左端点增加是数的删除*右端点增加是数的添加*每个数进出各一次而已2022年年12月月7日日清清华大学大学 张昆昆玮99*关键在于合理的计算方式使得相邻区间的差异尽量小*从一个区间变为另一个区间的代价是多少？*把区间看作二维平面的坐标*代价就是两个平面点的Manhattan距离！*然后呢？Hamilton路？*不！一个已知的区间可以用来算很多个未知的！*平面图Manhattan距离最小生成树。2022年年12月月7日日清清华大学大学 张昆昆玮100*平面图M

32、anhattan距离MST可以在O(nlogn)求出*先对Q个问题用这个方法处理*再按照MST的顺序和方法实际计算*求数学大牛分析总复杂度*虽然绕了很多弯路，但是有一种用模型解决实际问题的感觉。居然MST还能用来做预处理呢2022年年12月月7日日清清华大学大学 张昆昆玮101*听了这么久，一起做一道练习题吧*给定一列n个数，和m个区间，求每个区间里的众数出现了多少次。*对于10%的数据n100,m100对于30%的数据n1000,m1000对于50%的数据n100000,m100000对于70%的数据n1000000,m1000000以上数据中区间互不包含。*对于其余30%，n10000,m10000，区间可包含E-mail:2022年年12月月7日日清清华大学大学 张昆昆玮102*