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