统计的力量——线段树详细教程.pptx

清华大学张昆玮统计的力量——计算机算法可以分为两类:数值算法与非数值算法其中的非数值算法包括:索引分类统计……2019年11月9日清华大学张昆玮3一个悲剧POJ上的某题,时限很紧……大家都用树状数组,但是有人只会用线段树呢?而且我可以轻易改出一道不能用树状数组的题在线段树一次次TLE后,有一个ID发帖抱怨“下次写一个汇编版非递归线段树,再超时?”可是大家都知道,超时的代码已经2k了。其实我写的就是线段树。很快,而且不到1k。2019年11月9日清华大学张昆玮4线段树用于统计运行速度快适应能力强编写方便结构简单容易调试关键在于灵活实现线段树,从何而来?为什么在《算法导论》和黑书中都难见到其踪迹?2019年11月9日清华大学张昆玮52019年11月9日清华大学张昆玮6计算几何!计算几何在长期的发展中,诞生了许多实用的数据结构。区间查询,穿刺查询都是计算几何解决的问题作为特例中的特例,线段树解决的问题是:一维空间上的几何统计高维推广(kd-tree&…)可以进行正交查询由于竞赛中涉及计算几何的内容有限,不展开2019年11月9日清华大学张昆玮7真正有用的是“点树”线段树把数轴分成区间来处理如[8,10),[10,11),…实际上我们面对的往往是离散量竞赛中出现的线段树往往因此退化为“点树”即,最底层的线段只包含一个点:如:[8,9)中只有整点8而已在之后的讨论中,我们不再区别“点树”与线段树第一印象如果我给MM的第一印象不到80分的话……是不是老老实实地早点罢手比较好?2019年11月9日清华大学张昆玮82019年11月9日清华大学张昆玮9最经典的问题:区间和2019年11月9日清华大学张昆玮10核心思想:分治[1,4)in[0,4)左边,[1,2)in[0,2)Get1Get[2,4)in[2,4)虽然每次都有可能同时递归进入两棵子树,但每层实际上只访问了两个节点。为什么?因为查询是连续的啊……其实还有别的核心思想后面再讲……