统计的力量-线段树

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