统计的力量-线段树.ppt
清华大学 张昆玮,统计的力量线段树全接触,2023年10月17日,清华大学 张昆玮,2,许多算法的本质是统计,根据 D.E.Knuth 的分类方法计算机算法可以分为两类：数值算法与非数值算法其中的非数值算法包括：索引分类统计,2023年10月17日,清华大学 张昆玮,3,线段树？,大家都说：常数很大？不好写？难调试？想不到？,2023年10月17日,清华大学 张昆玮,4,一个悲剧,POJ上的某题，时限很紧大家都用树状数组，但是有人只会用线段树呢？而且我可以轻易改出一道不能用树状数组的题在线段树一次次TLE后，有一个ID发帖抱怨“下次写一个汇编版非递归线段树，再超时？”可是大家都知道，超时的代码已经2k了。其实我写的就是线段树。很快，而且不到1k。,2023年10月17日,清华大学 张昆玮,5,线段树用于统计,运行速度快适应能力强编写方便结构简单容易调试关键在于灵活实现,线段树，从何而来？,为什么在算法导论和黑书中都难见到其踪迹？,2023年10月17日,清华大学 张昆玮,6,2023年10月17日,清华大学 张昆玮,7,计算几何！,计算几何在长期的发展中，诞生了许多实用的数据结构。区间查询，穿刺查询都是计算几何解决的问题作为特例中的特例，线段树解决的问题是：一维空间上的几何统计高维推广（kd-tree&）可以进行正交查询由于竞赛中涉及计算几何的内容有限，不展开,2023年10月17日,清华大学 张昆玮,8,真正有用的是“点树”,线段树把数轴分成区间来处理如8,10),10,11),实际上我们面对的往往是离散量竞赛中出现的线段树往往因此退化为“点树”即，最底层的线段只包含一个点：如：8,9)中只有整点8而已在之后的讨论中，我们不再区别“点树”与线段树,第一印象,如果我给MM的第一印象不到80分的话是不是老老实实地早点罢手比较好？,2023年10月17日,清华大学 张昆玮,9,2023年10月17日,清华大学 张昆玮,10,最经典的问题：区间和,2023年10月17日,清华大学 张昆玮,11,核心思想：分治,1,4)in 0,4)左边，1,2)in 0,2)Get 1Get 2,4)in 2,4)虽然每次都有可能同时递归进入两棵子树，但每层实际上只访问了两个节点。为什么？因为查询是连续的啊,其实还有别的核心思想后面再讲,2023年10月17日,清华大学 张昆玮,12,因为查询是连续的？,如果同一层有三个被访问，依次为A，B，C查询是连续的，有了A和C，就一定包括B在树中的兄弟那我直接用B的父亲来计算好了，为什么要用B？,为什么用线段树？,功利点说，没啥用的东西咱不学,2023年10月17日,清华大学 张昆玮,13,且慢,直接把原数组处理成前缀和For i=2 to n doAi+=Ai-1Ans(a,b)=Aa-Ab-1,区区区间和，用的着线段树？,2023年10月17日,清华大学 张昆玮,14,2023年10月17日,清华大学 张昆玮,15,这是为什么呢？,原因是区间和的性质非常好满足区间减法区间减法什么的最讨厌了！后面再说！不过直接前缀和不是万能的！如果修改元素的话,2023年10月17日,清华大学 张昆玮,16,真正的作用,沟通原数组与前缀和的桥梁,其实（其实什么，后面再讲）,怎么写？,这个问题，本来是仁者见仁，智者见智的啊但是我要讲一点不那么“本来”的东西,2023年10月17日,清华大学 张昆玮,17,2023年10月17日,清华大学 张昆玮,18,朴素的递归算法,访问线段如果要的是整条线段就直接返回如果与左子线段相交就递归处理如果与右子线段相交就递归处理合并所得到的解遗憾的是，这种朴素的方法并不是那么容易实现而且存在严重的效率问题（常数太大）,怎么办？,2023年10月17日,清华大学 张昆玮,19,TLE,从存储方式讲起,工欲善其事，必先利其器。,2023年10月17日,清华大学 张昆玮,20,2023年10月17日,清华大学 张昆玮,21,几个不那么重要的问题,虽然可以设计出三叉，四叉，线段树但是我们先从二叉树开始登高必自迩，行远必自卑多叉怎么办后面再讲（这还要讲？自己研究去）为了不处理各种特殊情况，假设二叉树是满的！不是满的？你的总区间是0,1000)？你就当作0,1024)不就好了？,2023年10月17日,清华大学 张昆玮,22,堆式存储是关键,指针退休了？后面再讲,2023年10月17日,清华大学 张昆玮,23,一些简单的问题,N 的左儿子是 2NN 的右儿子是 2N+1N 的父亲是 N 1不就是个堆存储么？不用讲了吧？,2023年10月17日,清华大学 张昆玮,24,换成二进制看看吧！,2023年10月17日,清华大学 张昆玮,25,似曾相识？,字母树！存放的是100,101,110,111四个串！每个节点存的是以这个节点为前缀的所有节点和例：1中存的是所有四个以1开头的和。似乎从 100 到 111 就正好是原数组貌似下标减 4 就行了？,2023年10月17日,清华大学 张昆玮,26,好多性质啊，有用么？,我们可以直接找到一个数对应的叶子不用自顶向下慢慢地找啊找“直接加 4”多简单！直接找到叶子？无限遐想中,存下来了，然后呢？,可以直接找到叶子？,2023年10月17日,清华大学 张昆玮,27,2023年10月17日,清华大学 张昆玮,28,天然的非递归方法！,2023年10月17日,清华大学 张昆玮,29,天然的非递归方法！,2023年10月17日,清华大学 张昆玮,30,这么简单？,Func Query(s,t)/询问从s到t闭区间s=s 1,t=t+1;/变为开区间s+=M,t+=M;/找到叶子位置While not(s xor t)=1)doIf(s and 1)=0)Answer+=Trees+1;If(t and 1)=1)Answer+=Treet 1;s=s 1,t=t 1;,2023年10月17日,清华大学 张昆玮,31,C语言更简单！,for(s=s+M-1,t=t+M+1;st1;s=1,t=1)if(s,2023年10月17日,清华大学 张昆玮,32,Warning,在将闭区间转化成开区间的时候可能越界1理论上能放 0,2N)的树其实只能查询 1,2N-2 的范围切记切记,2023年10月17日,清华大学 张昆玮,33,不要紧张,如果需要查询 0 就整个向后平移一下所有下标加一！如果需要在0,1024)中查询1023结尾的区间？慢！你的数据规模不是 1000 么？如果真的要到1023，直接把总区间变成0,2048)就是这么狠！,2023年10月17日,清华大学 张昆玮,34,修改就更简单,Func Change(n,NewValue)n+=M;Treen=NewValue;While n 1 don=n 1;Treen=Tree2n+Tree2n+1;,2023年10月17日,清华大学 张昆玮,35,C语言更简单,for(Tn+=M=V,n=1;n;n=1)Tn=Tn+n+Tn+n+1;没了？没了。,2023年10月17日,清华大学 张昆玮,36,技术参数？,仅使用了两倍原数组的空间其中还完整地包括了原数组构造容易:For i=M-1 downto 1 do Ti=T2i+T2i+1;太好写了！好理解！自底向上，只访问一次，而且不一定访问到顶层实践中非常快，与树状数组接近为什么呢？后面再讲。,2023年10月17日,清华大学 张昆玮,37,人家树状数组只用一倍空间,因为树状数组依赖于区间减法区间减法什么的，最讨厌了后面再讲，再讲反正如果只问问前缀和，不问区间和的话那我也可以只用一倍空间！,2023年10月17日,清华大学 张昆玮,38,天然的非递归方法！,2023年10月17日,清华大学 张昆玮,39,天然的非递归方法！,2023年10月17日,清华大学 张昆玮,40,天然的非递归方法！,2023年10月17日,清华大学 张昆玮,41,所有右儿子没有用了,2023年10月17日,清华大学 张昆玮,42,省了一半空间吧,这不就和树状数组一样了？本来就应该一样。回过头说，树状数组究竟是什么？就是省掉一半空间后的线段树加上中序遍历计算位置需要lowbit什么的我们用的是先序遍历，符合人的思考习惯。,但是，这个空间没必要省。费点空间能换来实现的绝对简单。,2023年10月17日,清华大学 张昆玮,43,哈哈,2023年10月17日,清华大学 张昆玮,44,Just For Fun,我之前用这种写法做过不少题大家都说我的代码看不懂我说这就是一个树状数组写树状数组的人说没有lowbit我说那就算是线段树吧大家不相信非递归的线段树这么短我：,标记的传递与收集,懒惰即美德。,2023年10月17日,清华大学 张昆玮,45,区间修改,噩梦的开始,2023年10月17日,清华大学 张昆玮,46,2023年10月17日,清华大学 张昆玮,47,带区间修改的RMQ,RMQ(Range Minimum Query)区间最小值查询线段树支持区间修改：某一区间的数值全部增加一个可正可负的数暴力修改不灵了！,2023年10月17日,清华大学 张昆玮,48,四两拨千斤,在线段树上的每个节点增加一个标记表示这一区间被增加过多少在自顶而下的递归过程中如果看到标记，就更新当前节点的值并将标记下传嗯？又要自顶向下？,2023年10月17日,清华大学 张昆玮,49,标记永久化,其实堆式存储也可以自顶向下访问就是上下各走一次而已但是我们有更好的办法（使劲想想就知道了）不再下传标记，而是随用随查在自底向上的查询过程中每向上走一层，就按照对应的标记调整答案仔细想想很有道理。我们愿意把尽可能多的信息存放在树的根部，所以下传标记做什么？,常数很小：One Pass,永久化的标记就是值,庄周梦蝶而已,2023年10月17日,清华大学 张昆玮,50,2023年10月17日,清华大学 张昆玮,51,染色问题,一根线段，支持区间染色。询问区间是否同色？区间染色需要使用染色标记1表示红色，2表示蓝色，3绿色，0杂色询问的时候就直接看标记嘛,2023年10月17日,清华大学 张昆玮,52,直接看标记？,2为红色，3为蓝色，1为杂色修改3为红色查询1，杂色？永久化的标记就是值啊！值是自动维护的啊！其实我们的修改算法在修改3的时候已经维护了1自底向上顺便重算所有遇到的节点标记即可If(Markx=0 and Mark2x=Mark2x+1)Markx=Mark2x;,2023年10月17日,清华大学 张昆玮,53,狗拿耗子，猫下岗了,回到区间修改的RMQ通俗地讲，标记就是一个相对的量既然有了标记，值还有什么用？或者说，如果值本身就是相对的，还需要标记？如果我让所有的数都从零开始变化，那标记永久化之后，所有值都恒为零啊！于是我们连值也不存了。永久化的标记就是值。,2023年10月17日,清华大学 张昆玮,54,什么意思？,每个节点不存区间最大值Tn了存放Mn=Tn-Tn1让每一个节点的值都减除它父亲的值区间修改就直接改Mn。查询就是从要查的节点开始一直加到根。Tn=Mn+Mn1+M1;遇到节点x，则 A=min(M2x,M2x+1)Mx+=A,M2x-=A,M2x+1-=A,2023年10月17日,清华大学 张昆玮,55,简单,Func Add_x(s,t,x)for(s=s+M-1,t=t+M+1;st1;s=1,t=1)if(s,2023年10月17日,清华大学 张昆玮,56,too 简单，too,Func Max(s,t)for(s=s+M-1,t=t+M+1;st1;s=1,t=1)LAns+=Ts,Rans+=Tt;if(s,2023年10月17日,清华大学 张昆玮,57,启示,差分是化绝对为相对的重要手段标记永久化后就是值，只不过这种值是相对的计算答案时可以利用从节点到根部的信息,2023年10月17日,清华大学 张昆玮,58,alternative,截至PPT制作时，大家用的线段树自顶向下居多在自顶向下的线段树中，标记往往不是永久化的对于RMQ，需要下传标记对于染色问题，需要下传并收集标记思想与这里我的方法差不多，实现上差别较大至少上下各访问一次，较慢参见其他资料,2023年10月17日,清华大学 张昆玮,59,还一个欠账,线段树是连接原数组和前缀和的桥梁桥梁两边同时取差分前缀和与差分互为逆运算因此线段树也是连接差分和原数组的桥梁如果要支持区间修改，单点查询无需使用标记，直接将原数组差分用线段树维护差分数组的前缀和即可。,其实什么现在可以讲了,2023年10月17日,清华大学 张昆玮,60,前缀和的前缀和？,不借助标记，支持区间修改和区间求和（原创）先差分后变成维护一个前缀和的前缀和别被吓到，前缀和的前缀和是什么SS1=S1=x1SS2=S1+=2x1+x2SS3=S1+S2+S3=3x1+2x2+x3=4(x1+x2+x3)-(1x1+2x2+3x3)多维护一个nxn的前缀和就行了。,数学啊数学！,2023年10月17日,清华大学 张昆玮,61,最长上升区间列,最长上升“区间列”在一个区间列中按顺序找出最多区间使得不重叠，单调增如 1,3 2,4 4,5 答案是1,3+4,5动态规划的可行决策是什么呢？如果要使上升列长度大于x，最后一个数最小是多少，记为fx维护fx支持点查询和区间修改。,2023年10月17日,清华大学 张昆玮,62,前缀min的逆运算,点查询：查询x处fx的值区间修改：x左边的所有超过K的值，变为K把x的左右换一下（囧）整个f-x就是单调减的一个单调减的序列可以看作是由一个普通序列经过前缀min得到的！前缀min的逆运算是什么呢？我们并不关心,2023年10月17日,清华大学 张昆玮,63,这样也行？,我们现在要维护的就是前缀min的逆运算后的原序列！可是我们甚至不知道前缀min的逆运算是什么不要紧，反正用不到。点查询：查询x处fx的值直接返回维护序列的前缀min区间修改：x左边的所有超过K的值，变为K把维护序列中的fx变为K,线段树，太灵活了！,2023年10月17日,清华大学 张昆玮,64,但是不要迷信线段树,不要迷恋哥，哥只是个传说,2023年10月17日,清华大学 张昆玮,65,2023年10月17日,清华大学 张昆玮,66,重要条件：区间加法,说了这么多，能使用线段树解决问题的关键：区间加法，即区间的“性质”由子区间完全决定包括但不仅限于求和，求最值，求染色状态这里的“性质”有点像动态规划的状态表示有时候，求的更多反而更容易最简单的例子：求区间第二最值如果实在不满足区间加法，就全完了,2023年10月17日,清华大学 张昆玮,67,不满足区间加法？,我们都知道线段树求区间平均值不难那求一个区间中位数试试？什么，还不难？那你再求个众数？,2023年10月17日,清华大学 张昆玮,68,不满足区间加法！,越来越难的原因很简单知道两区间的中位数，就知道和区间的中位数？知道各自众数有什么用？,2023年10月17日,清华大学 张昆玮,69,超越中位数K-th number,给定一列数，反复求区间第k大数。要求的更多反而更容易更容易线段树的每个区间必须保留更多的信息！每个区间中存下区间所有数的有序数组通过归并完成区间加法,2023年10月17日,清华大学 张昆玮,70,归并很慢,如果每做一次查询就归并若干个线段复杂度就会达到O(n)离散化！二分答案！变为求：x是区间第几大数？这可以分别二分查找若干线段得到。总复杂度O(nlogn+Q*log2n),另一种原创方法，后面再讲,2023年10月17日,清华大学 张昆玮,71,区间减法,如果有了区间减法线段树就能如虎添翼如“区间和”变成“前缀和”操作能简单不少同时也是能够使用树状数组的条件但这不是必需的（和区间加法比一比）,另一种核心思想,我说过后面要讲的嘛,2023年10月17日,清华大学 张昆玮,72,2023年10月17日,清华大学 张昆玮,73,堆？,维护一个数据结构支持整数插入取最大整数范围是065535好了,2023年10月17日,清华大学 张昆玮,74,刘汝佳老师的大招,堆当然可以但是刘汝佳老师的黑书上有大招！“分段哈希”分成若干段，存下“段里面有没有数”信息,2023年10月17日,清华大学 张昆玮,75,分段哈希,2023年10月17日,清华大学 张昆玮,76,多来几层如何,如果多来几层呢？3层？4层？到每个节点下面都只有两个点为止！我们得到了什么,2023年10月17日,清华大学 张昆玮,77,这也是线段树,2023年10月17日,清华大学 张昆玮,78,哈哈,平衡树 vs 线段树,不要折腾,2023年10月17日,清华大学 张昆玮,79,2023年10月17日,清华大学 张昆玮,80,一种似曾相识的感觉,维护一个数据结构支持整数插入整数删除取第k大的数（取最大最小什么的就不说了）查询数的排名查某数是否存在允许元素重复（为了难一点）整数范围是065535好了,2023年10月17日,清华大学 张昆玮,81,统计的力量！,平衡树么？线段树！统计0,65536)每个数的出现频率，记为fx整数插入，fx+整数删除，fx-查询数的排名，求前缀和取第k大的数（取最大最小什么的就不说了）给定前缀和，查找自顶向下，左边不够就向右走，否则向左。,2023年10月17日,清华大学 张昆玮,82,事半功倍,实测得到线段树用来处理这类问题非常快平衡树中最快的Size Balanced Tree用了4秒多线段树不到半秒全部出解。这还没有分别减去读入数据的时间。线段树使用刚刚所讲的实现，代码量极小，且调试非常简单。,2023年10月17日,清华大学 张昆玮,83,如果数据范围大呢？,离散化。不能离散化？呵呵后面再讲,2023年10月17日,清华大学 张昆玮,84,一种似曾相识的感觉,维护一个数据结构支持字符串插入字符串删除取第k大的字符串（取最大最小什么的就不说了）查询字符串的排名查某字符串是否存在,2023年10月17日,清华大学 张昆玮,85,带size域的字母树,这里的size域的维护方式和线段树如出一辙！排名的计算方法，和之前整数的线段树完全一样如果把字符串看作26进制数那字母树就是线段树？,2023年10月17日,清华大学 张昆玮,86,哈哈,2023年10月17日,清华大学 张昆玮,87,那为啥字母树省空间？,所有节点用指针记录儿子空间随用随开不是满二叉树，甚至不完全自顶向下处理所有问题线段树也可以这样数据范围再大，能比26N还大？,2023年10月17日,清华大学 张昆玮,88,线段树处理long int,就是一棵三十二层高的线段树指针式存储，节点像字母树一样动态生成支持插入删除选择等等复杂度是O(NlogM)，M是最大的数对于long int，M=32实测用了一秒多（还记得平衡树四秒多么？）自顶向下，只算前缀和，也不难写,不就是个二进制的字母树？,2023年10月17日,清华大学 张昆玮,89,可能的改进,像压缩字母树一样，会节约大量空间代价：不好写了删除一个数之后尝试回收已经分配的节点代价：略慢，不好写了树高动态化初始树高是1，只能放0每一次如果要放的数太大，增加一个根根的左儿子是当前的根，右儿子空。这个还实用！,平衡树 with 线段树,在天愿作比翼鸟，在地愿为连理枝,2023年10月17日,清华大学 张昆玮,90,2023年10月17日,清华大学 张昆玮,91,记得Size域么？,平衡树上很多信息可以像线段树一样维护平衡树就是一个会旋转的动态线段树！最简单的，比如size域,2023年10月17日,清华大学 张昆玮,92,NOI2005 维护数列,块状链表的伤心题，标准程序5k+维护一个数列，支持：区间增加一个数区间删除区间插入区间求和区间翻转,2023年10月17日,清华大学 张昆玮,93,平衡树与线段树,平衡树 splay 可以支持：区间删除区间插入线段树可以支持区间增加一个数区间求和把线段树的值放在平衡树的节点上,2023年10月17日,清华大学 张昆玮,94,转起来的线段树,每个节点表示它和子树的信息总和平衡树旋转时更新线段树的域哇，会动的线段树,2023年10月17日,清华大学 张昆玮,95,标记啊标记,既要区间修改又要区间求和使用自顶向下的标记下传即可为了处理区间反转增设一个bool值表示当前节点左右子树已经互换先把区间从树中splay出再处理要同时更改所有节点的反转标记？不记录反转标记，记录反转标记的标记（！）,2023年10月17日,清华大学 张昆玮,96,好综合的一道题,但是所有部分都是相对简单的！一点点写，只是很多很多小题而已,返璞归真,关于线段树，我们讲的已经太多了,2023年10月17日,清华大学 张昆玮,97,2023年10月17日,清华大学 张昆玮,98,再还一个欠账,K-th number 的另一个方法如果区间互不包含，将所有要求的区间排个序来算。用平衡树或线段树存下当前区间中的数然后向下一个区间移动左端点增加是数的删除右端点增加是数的添加每个数进出各一次而已,2023年10月17日,清华大学 张昆玮,99,如果相互可以包含呢？,关键在于合理的计算方式使得相邻区间的差异尽量小从一个区间变为另一个区间的代价是多少？把区间看作二维平面的坐标代价就是两个平面点的Manhattan距离！然后呢？Hamilton路？不！一个已知的区间可以用来算很多个未知的！平面图Manhattan距离最小生成树。,2023年10月17日,清华大学 张昆玮,100,然后呢？,平面图Manhattan距离MST可以在O(nlogn)求出先对Q个问题用这个方法处理再按照MST的顺序和方法实际计算求数学大牛分析总复杂度虽然绕了很多弯路，但是有一种用模型解决实际问题的感觉。居然MST还能用来做预处理呢,2023年10月17日,清华大学 张昆玮,101,最后的硬骨头，众数,听了这么久，一起做一道练习题吧给定一列n个数，和m个区间，求每个区间里的众数出现了多少次。对于10%的数据n100,m100对于30%的数据n1000,m1000对于50%的数据n100000,m100000对于70%的数据n1000000,m1000000以上数据中区间互不包含。对于其余30%，n10000,m10000，区间可包含,2023年10月17日,清华大学 张昆玮,102,谢谢大家,
