国家集训队2004论文集 薛矛

《国家集训队2004论文集 薛矛》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2004国家集训队论文薛矛解决动态统计问题的两把利刃——剖析线段树与矩形切割广东北江中学薛矛【关键字】线段树矩形树方块树线段切割矩形切割【摘要】本文从统计类型的问题出发，以更好地解决这类问题为目的，较详细地介绍了线段树的基本操作，改进和推广；矩形切割的思想以及具体的使用方法。并通过将线段树和矩形切割进行对比，分析了线段树和矩形切割的复杂度，优缺点等，提出了它们各自的适用范围，并总结出何时使用最合适。【目录】一、引言................................................................................

2、....................................................2二、线段树................................................................................................................................22.1线段树的结构................................................................................................

3、..............22.2线段树的建立..............................................................................................................32.3线段树中的线段插入和删除......................................................................................32.3.1线段的插入.............................................

4、...........................................................32.3.2线段的删除........................................................................................................42.4线段树的简单应用......................................................................................................42.5

5、线段树的改进..............................................................................................................52.6线段树的推广..............................................................................................................92.7线段树小结...............................................

6、.................................................................10三、矩形切割..........................................................................................................................103.1线段切割........................................................................................

7、............................103.1.1线段的数据结构..............................................................................................113.1.2判断线段相交的函数......................................................................................113.1.3切割线