动态统计问题.pdf

解决动态统计问题的两把利刃 ——剖析线段树与矩形切割 广东北江中学 薛矛 【关键字】 线段树 矩形树 方块树 线段切割 矩形切割 【摘要】 本文从统计类型的问题出发，以更好地解决这类问题为目的，较详细地介绍了线 段树的基本操作，改进和推广；矩形切割的思想以及具体的使用方法。并通过将线段 树和矩形切割进行对比，分析了线段树和矩形切割的复杂度，优缺点等，提出了它们 各自的适用范围，并总结出何时使用最合适。 【目录】 一、引言2 二、线段树2 2.1 线段树的结构2 2.2 线段树的建立3 2.3 线段树中的线段插入和删除3 2.3.1 线段的插入3 2.3.2 线段的删除4 2.4 线段树的简单应用4 2.5 线段树的改进5 2.6 线段树的推广 8 2.7 线段树小结 10 三、矩形切割 10 3.1 线段切割 10 3.1.1 线段的数据结构 11 3.1.2 判断线段相交的函数 11 3.1.3 切割线段的过程 11 3.2 矩形切割 12 3.3 矩形切割的推广 13 3.4 矩形切割的应用 15 四、线段树与矩形切割的比较16 4.1 线段树的时空复杂度 16 4.1.1 线段树的空间复杂度 16 4.1.2 线段树的时间复杂度 17 4.2 矩形切割的时空复杂度 17 4.2.1 矩形切割的空间复杂度 17 4.2.2 矩形切割的时间复杂度 18 4.3 线段树与矩形切割适用范围的比较18 五、总结 19 - 1 - 【正文】 一、引言 我们在做练习和比赛中，经常能碰见统计类型的题目。题目通过输入数据给程序 提供事物信息，并要求程序能比较高效地求出某些时刻，某种情况下，事物的状态是 怎样的。这类问题往往比较简单明了，也能十分容易地写出模拟程序。但较大的数据 规模使得模拟往往不能满足要求。于是我们就要寻找更好的方法。本文将介绍解决此 类问题的两种方法——线段树与矩形切割。 二、线段树 线段树已经不是一个陌生的名词了，相信大家也对线段树比较熟悉，这里只做简 要的介绍。 2.1 线段树的结构 线段树是一棵二叉树，其结点是一条“线段”——[a,b]，它的左儿子和右儿子分别 是这条线段的左半段和右半段，即[a, (ab) / 2 ]和[ (ab) / 2 ,b]。线段树的叶子结     点是长度为1 的单位线段[a,a+1]。下图就是一棵根为[1,10]的线段树： [1,10] [1,5] [5,