统计的力量ppt课件.pptx

《统计的力量ppt课件.pptx》由会员分享，可在线阅读，更多相关《统计的力量ppt课件.pptx（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、清华大学 张昆玮*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮2*根据 D.E.Knuth 的分类方法计算机算法可以分为两类：*数值算法与非数值算法*其中的非数值算法包括：*索引*分类*统计*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮3*大家都说：*常数很大？*不好写？*难调试？*想不到？*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛

2、的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮4*POJ上的某题，时限很紧*大家都用树状数组，但是有人只会用线段树呢？*而且我可以轻易改出一道不能用树状数组的题*在线段树一次次TLE后，有一个ID发帖抱怨*“下次写一个汇编版非非递归线段树，再超时？”*可是大家都知道，超时的代码已经2k了。*其实我写的就是线段树。很快，而且不到1k。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮5*运行速度快*适应能力强*编写方便*结构简单*容易调试*关键在于

3、灵活灵活实现篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*为什么在算法导论和黑书中都难见到其踪迹？2022年年12月月30日日清清华大学大学 张昆昆玮6篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮7*计算几何在长期的发展中，诞生了许多实用的数据结构。*区间查询，穿刺查询都是计算几何解决的问题*作为特例中的特例，线段树解决的问题是：*一维空间上的几何统计*高维推广（kd-tree&）可以进行正交查询*由于竞赛中涉及计算

4、几何的内容有限，不展开篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮8*线段树把数轴分成区间来处理*如8,10),10,11),*实际上我们面对的往往是离散量*竞赛中出现的线段树往往因此退化为“点树”*即，最底层的线段只包含一个点：*如：8,9)中只有整点8而已*在之后的讨论中，我们不再区别“点树”与线段树篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*如果我给MM的第一印象不到80分的话是不是老老实实地早点罢手比较好？

5、2022年年12月月30日日清清华大学大学 张昆昆玮9篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮10*0,4)0,2)012,4)231,4)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮11*1,4)in 0,4)*左边，1,2)in 0,2)*Get 1*Get 2,4)in 2,4)*虽然每次都有可能同时递归进入两棵子树，但每层实际上只访问了两个节点。为什么

6、？*因为查询是连续的啊篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮12*ABC如果同一层有三个被访问，依次为A，B，C查询是连续的，有了A和C，就一定包括B在树中的兄弟那我直接用B的父亲来计算好了，为什么要用B？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*功利点说，没啥用的东西咱不学2022年年12月月30日日清清华大学大学 张昆昆玮13篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计

7、时计分系统是一种得分类型的系统*直接把原数组处理成前缀和*For i=2 to n do*Ai+=Ai-1*Ans(a,b)=Aa-Ab-1区区区间和，用的着线段树？2022年年12月月30日日清清华大学大学 张昆昆玮14篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮15*原因是区间和的性质非常好*满足区区间减法减法*区间减法什么的最讨厌了！后面再说！*不过直接前缀和不是万能的！*如果修改元素的话篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系

8、统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮16*数据数据结构构修改元素修改元素取前取前缀和和直接存储原数组O(1)O(n)直接存储前缀和O(n)O(1)线段树O(logn)O(logn)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*这个问题，本来本来是仁者见仁，智者见智的啊但是我要讲一点不那么“本来本来”的东西2022年年12月月30日日清清华大学大学 张昆昆玮17篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日

9、清清华大学大学 张昆昆玮18*访问线段*如果要的是整条线段就直接返回*如果与左子线段相交就递归处理*如果与右子线段相交就递归处理*合并所得到的解*遗憾的是，这种朴素的方法并不是那么容易并不是那么容易实现*而且存在严重的效率问题（常数太大）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*2022年年12月月30日日清清华大学大学 张昆昆玮19篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*工欲善其事，必先利其器。2022年年12月月30日日清清华大学大学 张昆昆玮20篮球比

10、赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮21*虽然可以设计出三叉，四叉，线段树*但是我们先从二叉二叉树开始*登高必自迩，行远必自卑*多叉怎么办后面再讲（这还要讲？自己研究去）*为了不处理各种特殊情况，假设二叉树是满的！*不是满的？你的总区间是0,1000)？*你就当作0,1024)不就好了？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮22*1245367篮球比赛是根据

11、运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮23*N 的左儿子是 2N*N 的右儿子是 2N+1*N 的父亲是 N 1*不就是个堆存储么？不用讲了吧？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮24*1 1010010111110111篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学

12、大学 张昆昆玮25*字母树！*存放的是100,101,110,111四个串！*每个节点存的是以这个节点为前缀的所有节点和*例：1中存的是所有四个以1开头的和。*似乎从 100 到 111 就正好是原数组*貌似下标减 4 就行了？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮26*我们可以直接找到一个数对应的叶子*不用自顶向下慢慢地找啊找*“直接加 4”多简单！*直接找到叶子？*无限遐想中篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得

13、分类型的系统*可以直接找到叶子？2022年年12月月30日日清清华大学大学 张昆昆玮27篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮28*124895101136121371415(0,5)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮29*124895101136121371415(0,5)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比

14、赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮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月月30日日清清华大学大学 张昆昆玮31*for(s=s+M

15、-1,t=t+M+1;st1;s=1,t=1)*if(s&1)Ans+=Ts1;*if(t&1)Ans+=Tt1;*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮32*在将闭区间转化成开区间的时候可能越界1*理论上能放 0,2N)的树*其实只能查询 1,2N-2 的范围*切记切记篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮33*如果需要查询 0 就整个向后平移一下*所

16、有下标加一！*如果需要在0,1024)中查询1023结尾的区间？*慢！你的数据规模不是 1000 么？*如果真的要到1023，直接把总区间变成0,2048)*就是这么狠！篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮34*Func Change(n,NewValue)*n+=M;*Treen=NewValue;*While n 1 do*n=n 1;*Treen =Tree2n+Tree2n+1;篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系

17、统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮35*for(Tn+=M=V,n=1;n;n=1)*Tn=Tn+n+Tn+n+1;*没了？*没了。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮36*仅使用了两倍原数组的空间*其中还完整地包括了原数组*构造容易:*For i=M-1 downto 1 do Ti=T2i+T2i+1;*太好写了！好理解！*自底向上，只访问一次，而且不一定访问到顶层*实践中非常快，与树状数组接近*为什么呢？后面再讲。篮球比赛是根

18、据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮37*因为树状数组依赖于区间减法*区间减法什么的，最讨厌了后面再讲，再讲*反正如果只问问前缀和，不问区间和的话*那我也可以只用一倍空间！篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮38*124895101136121371415(,5)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分

19、类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮39*124895101136121371415(,5)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮40*124895101136121371415(,5)?篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮41*1-No2-14-25-No3-No6-37-No篮球比赛是根据运动队在规定的比赛时间里得分多少

20、来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮42*这不就和树状数组一样了？*本来就应该一样。*回过头说，树状数组究竟是什么？*就是省掉一半空间后的线段树加上中序遍历*计算位置需要lowbit什么的*我们用的是先序遍历，符合人的思考习惯。但是，这个空间没必要省。费点空间能换来实现的绝对简单。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮43*树状数组线段树篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，

21、因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮44*我之前用这种写法做过不少题*大家都说我的代码看不懂*我说这就是一个树状数组*写树状数组的人说没有lowbit*我说那就算是线段树吧*大家不相信非递归的线段树这么短*我：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*懒惰即美德。2022年年12月月30日日清清华大学大学 张昆昆玮45篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*噩梦的开始2022年年12月月30日日

22、清清华大学大学 张昆昆玮46篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮47*RMQ(Range Minimum Query)*区间最小值查询*线段树*支持区间修改：*某一区间的数值全部增加一个可正可负的数*暴力修改不灵了！篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮48*在线段树上的每个节点增加一个标记*表示这一区间被增加过多少*在自顶而下的递归过程中*如果看到标

23、记，就更新当前节点的值*并将标记下传*嗯？又要自顶向下？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮49*其实堆式存储也可以自顶向下访问*就是上下各走一次而已*但是我们有更好的办法（使劲想想就知道了）*不再下不再下传标记，而是随用随查*在自底向上的查询过程中*每向上走一层，就按照对应的标记调整答案*仔细想想很有道理。我们愿意把尽可能多的信息存放在树的根部，所以下传标记做什么？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系

24、统*庄周梦蝶而已2022年年12月月30日日清清华大学大学 张昆昆玮50篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮51*一根线段，支持区间染色。询问区间是否同色？*区间染色需要使用染色标记1表示红色，2表示蓝色，3绿色，0杂色*询问的时候就直接看标记嘛篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮52*2为红色，3为蓝色，1为杂色修改3为红色查询1，杂色？*永久永久

25、化的化的标记就是就是值啊啊！值是自动维护的啊！*其实我们的修改算法在修改3的时候已经维护了1*自底向上顺便重算所有遇到的节点标记即可*If(Markx=0 and Mark2x=Mark2x+1)*Markx=Mark2x;篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮53*回到区间修改的RMQ*通俗地讲，标记就是一个相对的量*既然有了标记，值还有什么用？*或者说，如果值本身就是相对的，还需要标记？*如果我让所有的数都从零开始变化，那标记永久化之后，所有值都恒为零啊！*于是我们连值

26、也不存了。永久化的标记就是值。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮54*每个节点不存区间最大值Tn了存放Mn=Tn-Tn1*让每一个节点的值都减除它父亲的值*区间修改就直接改Mn。*查询就是从要查的节点开始一直加到根。Tn=Mn+Mn1+M1;*遇到节点x，则 A=min(M2x,M2x+1)Mx+=A,M2x-=A,M2x+1-=A篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清

27、华大学大学 张昆昆玮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月月30日日清清华大学大学 张昆昆玮56*Func Max(s,t)*for(s=s+M-1,t=t+M+1;st1;s=1,t=1)*LAns+=

28、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月月30日日清清华大学大学 张昆昆玮57*差分是化绝对为相对的重要手段*标记永久化后就是值，只不过这种值是相对的*计算答案时可以利用从节点到根部的信息篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统202

29、2年年12月月30日日清清华大学大学 张昆昆玮58*截至PPT制作时，大家用的线段树自顶向下居多*在自顶向下的线段树中，标记往往不是永久化的*对于RMQ，需要下传标记*对于染色问题，需要下传并收集标记*思想与这里我的方法差不多，实现上差别较大*至少上下各访问一次，较慢*参见其他资料篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮59*线段树是连接原数组和前缀和的桥梁*桥梁两边同时取差分*前缀和与差分互为逆运算*因此线段树也是连接差分和原数组的桥梁*如果要支持区间修改，单点查询*无需使

30、用标记，直接将原数组差分*用线段树维护差分数组的前缀和即可。讲了了篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮60*不借助标记，支持区间修改和区间求和（原创）*先差分后变成维护一个前缀和的前缀和*别被吓到，前缀和的前缀和是什么*SS1=S1 =x1*SS2=S1+=2x1+x2*SS3=S1+S2+S3=3x1+2x2+x3 =4(x1+x2+x3)-(1x1+2x2+3x3)*多维护一个nxn的前缀和就行了。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球

31、比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮61*最长上升“区间列”*在一个区间列中按顺序找出最多区间使得不重叠，单调增*如 1,3 2,4 4,5 答案是1,3+4,5*动态规划的可行决策是什么呢？如果要使上升列长度大于x，最后一个数最小是多少，记为fx*维护fx支持点查询和区间修改。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮62*点查询：查询x处fx的值*区间修改：x左边的所有超过K的值，变为K*把x的左右换一下（囧）*整个f-

32、x就是单调减的*一个单调减的序列可以看作是由一个普通序列经过前缀min得到的！*前缀min的逆运算是什么呢？*我们并不关心篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮63*我们现在要维护的就是前缀min的逆运算后的原序列！*可是我们甚至不知道前缀min的逆运算是什么*不要紧，反正用不到。*点查询：查询x处fx的值直接返回维护序列的前缀min*区间修改：x左边的所有超过K的值，变为K把维护序列中的fx变为K篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的

33、计时计分系统是一种得分类型的系统*2022年年12月月30日日清清华大学大学 张昆昆玮64篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*不要迷恋哥，哥只是个传说2022年年12月月30日日清清华大学大学 张昆昆玮65篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮66*说了这么多，能使用线段树解决问题的关键：*区间加法，即区间的“性质”由子区间完全决定*包括但不仅限于求和，求最值，求染色状态*这里的“性质”有点像动态规划

34、的状态表示*有时候，求的更多反而更容易*最简单的例子：求区间第二最值*如果实在不满足区间加法，就全完了篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮67*我们都知道线段树求区间平均值不难*那求一个区间中位数试试？*什么，还不难？*那你再求个众数？*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮68*越来越难的原因很简单*知道两区间的中位数，就知道和区间的中位数？*知道各

35、自众数有什么用？*篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮69*给定一列数，反复求区间第k大数。*要求的更多反而更容易更容易*线段树的每个区间必须保留更多的信息！*每个区间中存下区间所有数的有序数组*通过归并完成区间加法篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮70*如果每做一次查询就归并若干个线段*复杂度就会达到O(n)*离散化！二分答案！*变为求：x是区间

36、第几大数？*这可以分别二分查找若干线段得到。*总复杂度O(nlogn+Q*log2n)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮71*如果有了区间减法*线段树就能如虎添翼*如“区间和”变成“前缀和”*操作能简单不少*同时也是能够使用树状数组的条件*但这不是必需的（和区间加法比一比）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*我说过后面要讲的嘛2022年年12月月30日日清清华大学大学 张昆昆玮72篮球比赛是根据运

37、动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮73*维护一个数据结构支持*整数插入*取最大*整数范围是065535好了篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮74*堆当然可以*但是刘汝佳老师的黑书上有大招！*“分段哈希”*分成若干段，存下“段里面有没有数”信息篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年1

38、2月月30日日清清华大学大学 张昆昆玮75*0,65536)0,256)0255篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮76*如果多来几层呢？*3层？4层？*到每个节点下面都只有两个点为止！*我们得到了什么篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮77*0,4)0,2)012,4)23篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的

39、计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮78*分段哈希线段树篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*不要折腾2022年年12月月30日日清清华大学大学 张昆昆玮79篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮80*维护一个数据结构支持*整数插入*整数删除*取第k大的数（取最大最小什么的就不说了）*查询数的排名*查某数是否存在*允许元素重复（为了难一点）*整数范围是06

40、5535好了篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮81*平衡树么？线段树！*统计0,65536)每个数的出现频率，记为fx*整数插入，fx+*整数删除，fx-*查询数的排名，求前缀和*取第k大的数（取最大最小什么的就不说了）给定前缀和，查找自顶向下，左边不够就向右走，否则向左。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮82*实测得到线段树用来处理这类问题非常

41、快*平衡树中最快的Size Balanced Tree用了4秒多*线段树不到半秒全部出解。*这还没有分别减去读入数据的时间。*线段树使用刚刚所讲的实现，*代码量极小，且调试非常简单。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮83*离散化。*不能离散化？*呵呵后面再讲篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮84*维护一个数据结构支持*字符串插入*字符串删除*取第

42、k大的字符串（取最大最小什么的就不说了）*查询字符串的排名*查某字符串是否存在篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮85*这里的size域的维护方式*和线段树如出一辙！*排名的计算方法，和之前整数的线段树完全一样*如果把字符串看作26进制数*那字母树就是线段树？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮86*字母树线段树篮球比赛是根据运动队在规定的比赛时间里

43、得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮87*所有节点用指针记录儿子*空间随用随开*不是满二叉树，甚至不完全*自顶向下处理所有问题*线段树也可以这样*数据范围再大，能比26N还大？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮88*就是一棵三十二层高的线段树指针式存储，节点像字母树一样动态生成*支持插入删除选择等等*复杂度是O(NlogM)，M是最大的数*对于long int，M=32*实测用了一秒多

44、*（还记得平衡树四秒多么？）*自顶向下，只算前缀和，也不难写篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮89*像压缩字母树一样，会节约大量空间代价：不好写了*删除一个数之后尝试回收已经分配的节点代价：略慢，不好写了*树高动态化初始树高是1，只能放0每一次如果要放的数太大，增加一个根根的左儿子是当前的根，右儿子空。这个还实用！篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统*在天愿作比翼鸟，在地愿为连理枝2022年年12月

45、月30日日清清华大学大学 张昆昆玮90篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮91*平衡树上很多信息可以像线段树一样维护*平衡树就是一个会旋转的动态线段树！*最简单的，比如size域篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮92*块状链表的伤心题，标准程序5k+*维护一个数列，支持：*区间增加一个数*区间删除*区间插入*区间求和*区间翻转篮球比赛是根据运动队在

46、规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮93*平衡树 splay 可以支持：*区间删除*区间插入*线段树可以支持*区间增加一个数*区间求和*把线段树的值放在平衡树的节点上篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮94*每个节点表示它和子树的信息总和*平衡树旋转时更新线段树的域*哇，会动的线段树篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是

47、一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮95*既要区间修改又要区间求和使用自顶向下的标记下传即可*为了处理区间反转增设一个bool值表示当前节点左右子树已经互换*先把区间从树中splay出再处理*要同时更改所有节点的反转标记？不记录反转标记，记录反转标记的标记（！）篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮96*但是所有部分都是相对简单的！*一点点写，只是很多很多小题而已篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计

48、时计分系统是一种得分类型的系统*关于线段树，我们讲的已经太多了2022年年12月月30日日清清华大学大学 张昆昆玮97篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮98*K-th number 的另一个方法*如果区间互不包含，将所有要求的区间排个序来算。*用平衡树或线段树存下当前区间中的数*然后向下一个区间移动*左端点增加是数的删除*右端点增加是数的添加*每个数进出各一次而已篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统

49、2022年年12月月30日日清清华大学大学 张昆昆玮99*关键在于合理的计算方式使得相邻区间的差异尽量小*从一个区间变为另一个区间的代价是多少？*把区间看作二维平面的坐标*代价就是两个平面点的Manhattan距离！*然后呢？Hamilton路？*不！一个已知的区间可以用来算很多个未知的！*平面图Manhattan距离最小生成树。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮100*平面图Manhattan距离MST可以在O(nlogn)求出*先对Q个问题用这个方法处理*再按照MS

50、T的顺序和方法实际计算*求数学大牛分析总复杂度*虽然绕了很多弯路，但是有一种用模型解决实际问题的感觉。居然MST还能用来做预处理呢篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2022年年12月月30日日清清华大学大学 张昆昆玮101*听了这么久，一起做一道练习题吧*给定一列n个数，和m个区间，求每个区间里的众数出现了多少次。*对于10%的数据n100,m100对于30%的数据n1000,m1000对于50%的数据n100000,m100000对于70%的数据n1000000,m1000000以上数据中区间互不包含。*对于其余30%