统计的力量

清华大学张昆玮*2020年6月22日清华大学张昆玮2**根据D.E.Knuth的分类方法计算机算法可以分为两类：*数值算法与非数值算法*其中的非数值算法包括：*索引*分类*统计*……2020年6月22日清华大学张昆玮3**大家都说：*……*常数很大？*不好写？*难调试？*想不到？*……2020年6月22日清华大学张昆玮4**POJ上的某题，时限很紧……*大家都用树状数组，但是有人只会用线段树呢？*而且我可以轻易改出一道不能用树状数组的题*在线段树一次次TLE后，有一个ID发帖抱怨*“下次写一个汇编版非递归线段树，再超时？”*可是大家都知道，超时的代码已经2k了。*其实我写的就是线段树。很快，而且不到1k。2020年6月22日清华大学张昆玮5**运行速度快*适应能力强*编写方便*结构简单*容易调试*关键在于灵活实现*为什么在《算法导论》和黑书中都难见到其踪迹？2020年6月22日清华大学张昆玮62020年6月22日清华大学张昆玮7**计算几何在长期的发展中，诞生了许多实用的数据结构。*区间查询，穿刺查询都是计算几何解决的问题*作为特例中的特例，线段树解决的问题是：*一维空间上的几何统计*高维推广（kd-tree&…）可以进行正交查询*由于竞赛中涉及计算几何的内容有限，不展开2020年6月22日清华大学张昆玮8**线段树把数轴分成区间来处理*如[8,10),[10,11),…*实际上我们面对的往往是离散量*竞赛中出现的线段树往往因此退化为“点树”*即，最底层的线段只包含一个点：*如：[8,9)中只有整点8而已*在之后的讨论中，我们不再区别“点树”与线段树*如果我给MM的第一印象不到80分的话……是不是老老实实地早点罢手比较好？2020年6月22日清华大学张昆玮92020年6月22日清华大学张昆玮10*[0,4)[0,2)01[2,4)23[1,4)?2020年6月22日清华大学张昆玮11**[1,4)in[0,4)*左边，[1,2)in[0,2)*Get1*Get[2,4)in[2,4)*虽然每次都有可能同时递归进入两棵子树，但每层实际上只访问了两个节点。为什么？*因为查询是连续的啊……2020年6月22日清华大学张昆玮12*ABC如果同一层有三个被访问，依次为A，B，C查询是连续的，有了A和C，就一定包括B在树中的兄弟那我直接用B的父亲来计算好了，为什么要用B？*功利点说，没啥用的东西咱不学……2020年6月22日清华大学张昆玮13**直接把原数组处理成前缀和*Fori=2tondo*A[i]+=A[i-1]*Ans(a,b)=A[a]-A[b-1]区区区间和，用的着线段树？2020年6月22日清华大学张昆玮142020年6月22日清华大学张昆玮15**原因是区间和的性质非常好*满足区间减法*区间减法什么的最讨厌了！后面再说！*不过直接前缀和不是万能的！*如果修改元素的话……2020年6月22日清华大学张昆玮16*数据结构修改元素取前缀和直接存储原数组O(1)O(n)直接存储前缀和O(n)O(1)线段树O(logn)O(logn)*这个问题，本来是仁者见仁，智者见智的啊但是我要讲一点不那么“本来”的东西2020年6月22日清华大学张昆玮172020年6月22日清华大学张昆玮18**访问线段*如果要的是整条线段就直接返回*如果与左子线段相交就递归处理*如果与右子线段相交就递归处理*合并所得到的解*遗憾的是，这种朴素的方法并不是那么容易实现*而且存在严重的效率问题（常数太大）*2020年6月22日清华大学张昆玮19*工欲善其事，必先利其器。2020年6月22日清华大学张昆玮202020年6月22日清华大学张昆玮21**虽然可以设计出三叉，四叉，……线段树*但是我们先从二叉树开始*登高必自迩，行远必自卑*多叉怎么办后面再讲（这还要讲？自己研究去）*为了不处理各种特殊情况，假设二叉树是满的！*不是满的？你的总区间是[0,1000)？*你就当作[0,1024)不就好了？2020年6月22日清华大学张昆玮22*12453672020年6月22日清华大学张昆玮23**N的左儿子是2N*N的右儿子是2N+1*N的父亲是N1*……*不就是个堆存储么？不用讲了吧？2020年6月22日清华大学张昆玮24*110100101111101112020年6月22日清华大学张昆玮25**字母树！*存放的是100,101,110,111四个串！*每个节点存的是以这个节点为前缀的所有节点和*例：1中存的是所有四个以1开头的和。*似乎从100到111就正好是原数组*貌似……下标减4就行了？2020年6月22日清华大学张昆玮26**我们可以直接找到一个数对应的叶子*不用自顶向下慢慢地找啊找*“直接加4”多简单！*……*直接找到叶子？*无限遐想中……*可以直接找到叶子？2020年6月22日清华大学张昆玮272020年6月22日清华大学张昆玮28*124895101136121371415(0,5)?2020年6月22日清华大学张昆玮29*124895101136121371415(0,5)?2020年6月22日清华大学张昆玮30**FuncQuery(s,t)//询问从s到t闭区间*s=s–1,t=t+1;//变为开区间*s+=M,t+=M;//找到叶子位置*Whilenot((sxort)==1)do*If((sand1)==0)Answer+=Tree[s+1];*If((tand1)==1)Answer+=Tree[t–1];*s=s1,t=t1;2020年6月22日清华大学张昆玮31**for(s=s+M-1,t=t+M+1;s^t^1;s=1,t=1){*if(~s&1)Ans+=T[s^1];*if(t&1)Ans+=T[t^1];*}2020年6月22日清华大学张昆玮32**在将闭区间转化成开区间的时候可能越界1*理论上能放[0,2^N)的树*其实只能查询[1,2^N-2]的范围*切记切记2020年6月22日清华大学张昆玮33**如果需要查询0就整个向后平移一下*所有下标加一！*如果需要在[0,1024)中查询1023结尾的区间？*慢！你的数据规模不是1000么？*……*如果真的要到1023，直接把总区间变成[0,2048)*就是这么狠！2020年6月22日清华大学张昆玮34**FuncChange(n,NewValue)*n+=M;*Tree[n]=NewValue;*Whilen1do*n=n1;*Tree[n]=Tree[2n]+Tree[2n+1];2020年6月22日清华大学张昆玮35**for(T[n+=M]=V,n=1;n;n=1)*T[n]=T[n+n]+T[n+n+1];*没了？*没了。2020年6月22日清华大学张昆玮36**仅使用了两倍原数组的空间*其中还完整地包括了原数组*构造容易:*Fori=M-1downto1doT[i]=T[2i]+T[2i+1];*太好写了！好理解！*自底向上，只访问一次，而且不一定访问到顶层*实践中非常快，与树状数组接近*为什么呢？后面再讲。2020年6月22日清华大学张昆玮37**因为树状数组依赖于区间减法*区间减法什么的，最讨厌了……后面再讲，再讲*反正如果只问问前缀和，不问区间和的话*那我也可以只用一倍空间！2020年6月22日清华大学张昆玮38*124895101136121371415(…,5)?2020年6月22日清华大学张昆玮39*124895101136121371415(…,5)?2020年6月22日清华大学张昆玮40*124895101136121371415(…,5)?2020年6月22日清华大学张昆玮41*1-No2-14-25-No3-No6-37-No2020年6月22日清华大学张昆玮42**这不就和树状数组一样了？*本来就应该一样。*回过头说，树状数组究竟是什么？*就是省掉一半空间后的线段树加上中序遍历*计算位置需要lowbit什么的*我们用的是先序遍历，符合人的思考习惯。2020年6月22日清华大学张昆玮43*树状数组线段树2020年6月22日清华大学张昆玮44**我之前用这种写法做过不少题……*大家都说我的代码看不懂*我说这就是一个树状数组*写树状数组的人说没有lowbit*我说那就算是线段树吧*大家不相信非递归的线段树这么短……*我：……*懒惰即美德。2020年6月22日清华大学张昆玮45*噩梦的开始2020年6月22日清华大学张昆玮462020年6月22日清华大学张昆玮47**RMQ(RangeMinimumQuery)*区间最小值查询*线段树*支持区间修改：*某一区间的数值全部增加一个可正可负的数*暴力修改不灵了！2020年6月22日清华大学张昆玮48**在线段树上的每个节点增加一个标记*表示这一区间被增加过多少*在自顶而下的递归过程中*如果看到标记，就更新当前节点的值*并将标记下传*嗯？又要自顶向下？2020年6月22日清华大学张昆玮49**其实堆式存储也可以自顶向下访问*就是上下各走一次而已*但是我们有更好的办法（使劲想想就知道了）*不再下传标记，而是随用随查*在自底向上的查询过程中*每向上走一层，就按照对应的标记调整答案*仔细想想很有道理。我们愿意把尽可能多的信息存放在树的根部，所以下传标记做什么？*庄周梦蝶而已2020年6月22日清华大学张昆玮502020年6月22日清华大学张昆玮51**一根线段，支持区间染色。询问区间是否同色？*区间染色需要使用染色标记1表示红色，2表示蓝色，3绿色，0杂色*询问的时候就直接看标记嘛2020年6月22日清华大学张昆玮52**2为红色，3为蓝色，1为杂色修改3为红色查询1，杂色？*永久化的标记就是值啊！值是自动维护的啊！*其实我们的修改算法在修改3的时候已经维护了1*自底向上顺便重算所有遇到的节点标记即可*If(Mark[x]==0andMark[2x]==Mark[2x+1])*Mark[x]=Mark[2x];2020年6月22日清华大学张昆玮53**回到区间修改的RMQ*通俗地讲，标记就是一个相对的量*既然有了标记，值还有什么用？*或者说，如果值本身就是相对的，还需要标记？*如果我让所有的数都从零开始变化，那标记永久化之后，所有值都恒为零啊！*于是我们连值也不存了。永久化的标记就是值。2020年6月22日清华大学张昆玮54**每个节点不存区间最大值T[n]了存放M[n]=T[n]-T[n1]*让每一个节点的值都减除它父亲的值*区间修改就直接改M[n]。*查询就是从要查的节点开始一直加到根。T[n]=M[n]+M[n1]+…+M[1];*遇到节点x，则A=min(M[2x],M[2x+1])M[x]+=A,M[2x]-=A,M[2x+1]-=A2020年6月22日清华大学张昆玮55**FuncAdd_x(s,t,x)*for(s=s+M-1,t=t+M+1;s^t^1;s=1,t=1){*if(~s&1)T[s^1]+=x;*if(t&1)T[t^1]+=x;*A=min(T[s],T[s^1]),T[s]-=A,T[s^1]-=A,T[s1]+=A;*A=min(T[t],T[t^1]),T[t]-=A,T[t^1]-=A,T[t1]+=A;*}2020年6月22日清华大学张昆玮56**FuncMax(s,t)*for(s=s+M-1,t=t+M+1;s^t^1;s=1,t=1){*LAns+=T[s],Rans+=T[t];*if(~s&1)LAns=max(LAns,T[s^1]);*if(t&1)RAns=max(RAns,T[t^1]);*}*Ans=max(LAns,RAns);*while(s1)Ans+=T[s=1];2020年6月22日清华大学张昆玮57**差分是化绝对为相对的重要手段*标记永久化后就是值，只不过这种值是相对的*计算答案时可以利用从节点到根部的信息2020年6月22日清华大学张昆玮58**截至PP