论线段树在ACMICPC中的应用(1)

通化师范学院本科生毕业论文（2013届）题目：论线段树在ACM/ICPC中的应用系别：计算机科学系专业：计算机科学与技术班级：2009级3班作者姓名：王甲学号：200911050130指导教师：纪洪波职称：讲师学历：研究生论文成绩：2013年4月目录摘要.....................................................................1Abstract..................................................................1绪论..................................................................3第一章线段树的概念.......................................................41.1线段树是什么......................................................................................................................41.2线段树的性质......................................................................................................................41.3线段树的时间及空间效率分析..........................................................................................4第二章线段树的建立.......................................................52.1线段树结点定义..................................................................................................................52.2线段树的表示......................................................................................................................62.3线段树的建立......................................................................................................................6第三章线段树的操作.......................................................73.1插入操作..............................................................................................................................73.2删除操作..............................................................................................................................83.3点更新操作..........................................................................................................................83.4成段更新操作......................................................................................................................93.5询问操作............................................................................................................................10结束语.................................................................13参考文献.................................................................141论线段树在ACM/ICPC中的应用计算机科学与技术09级03班王甲摘要:近年来，涉及线段树的各种竞赛题越来越多，每一年的国际大学生程序设计竞赛（ACM/ICPC）题目都有需要或直接、或间接地用线段树优化甚至解决问题；而竞赛对选手运用线段树的要求也越来越高，已经不再停留于简单的式的查询与修改数据。本文讨论了线段树求解问题，优化问题的核心内容及其特点。线段树是一种特殊的二叉树的数据结构，它可以较为高效地实现在区间上的统计，查询以及修改等操作。主要内容是线段树的基本概念，线段树的构建，以及设计结点类型在ACM/ICPC中的应用。通过一些典型问题与具体例子的结合分析，来论证线段树在ACM/ICPC中的应用。关键字：线段树；数据结构；区间操作；ACM/ICPCTheApplicationoftheSegmentTreeintheACM/ICPCJiaWangClass3Grade2009DepartmentofComputerScienceAbstract:Inrecentyears,moreandmorecontestproblemsareinvolvedinsegmenttree,eachyearmostoftheproblemsinInternationalCollegiateProgrammingContest(ACM/ICPC)hasdirectorindirectconnectionwiththesegmenttree,contestersusethiskindoftechniquetooptimizeandsolvetheseproblems.Andtherequirementsofthecontesters’abilitythatusethe2segmenttreeinthecontestarealsoincreasing.It’snolongerstayinthelevelofthesimplequeryanddata-modify.Thispaperdiscusseshowtousethesegmenttreetooptimizeandsolvetheproblems,andthefeatureofthetechnique.Thesegmenttreeisaspecialkindofbinarytreedatastructure,itcanbemoreefficienttocompletetheoperationsaboutthequeryandmodificationontherange.Themaincontentsincludethebasicconceptsofthesegmenttree,howtobuildasegmenttree,andhowtodesignthenodetypesinthesegmenttree.Withthecombinationoftheanalysisofsometypicalproblemsandspecificproblems,thispaperdiscussestheapplicationofthesegmenttreeintheACM/ICPC.KeyWords:Segmenttree；DataStructure；IntervalOperation；ACM/ICPC3绪论国际大学生程序设计竞赛（AssociationofComputingMachineryInternationalCollegiateProgrammingContest简称ACM/ICPC）最早是由美国计算机协会举办的一些由计算机从业人员参加的比赛。从最早1970年第一届至今，经过四十余年的发展，该项赛事已经成为世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。在竞赛过程中体现的是大学生的创新能力、团队精神和在压力下编写程序、分析和解决问题的能力，也是大学计算机教育成果的直接体现。而在中国，随着中国代表队一次又一次夺得该项赛事的冠军，以及在获奖之后得以接触全国乃至全世界最顶尖的信息企业的机会，全国各大高校已然掀起了ACM的热潮。我校从2007年开始参加第一届吉林省大学生程序竞赛开始，已经有近七年的ACM比赛经验。有人说过一句名言，“程序=数据结构+算法”。算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法的掌握程度，就成了我们在同场赛事中能否获胜至关重要的一项技能；数据结构是指在程序设计中程序员对程序中所有数据资源的组织方式与方法。已有的一些传统算法与数据结构，大家已经有所了解，但是随着参赛人员竞赛水平的提高，竞赛题目的难度也是水涨船高，那些已有的知识已经不能解决或者不能完全解决问题。所以，我们迫切需要对已有的算法及数据结构进行改良优化，本文仅从数据结构中一个小分支—线段树进行阐述。4第一章线段树的概念1.1线段树是什么我们从直观上来看下一棵线段树到底长什么样，它表示一棵区间是[1,10]的线段树：[1,10][1,5][6,10][1,3][4,5][6,8][9,10][3,3][4,4][5,5][6,7][8,8][9,9][1,2][10,10][1,1][2,2][6,6][7,7]相信看完以后大家就可以稍微知道线段树的本质了，下面给出线段树的定义：线段树是一棵二叉树，树中的每一个结点表示一个区间[a,b]。每一个叶子节点表示一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。且新建完一棵线段树后，叶子结点一定有且只有(b-a+1)个。1.2线段树的性质由1.1节知，线段树是一查完全二叉树，所以完全二叉树的性质也完全适用于线段树，定理：线段树把区间上的任意一条线段都分成不超过2*()22logrl条线段1.3线段树的时间及空间效率分析思考一下代表区间为[1,L]的线段树需要多少个节点，不断二分，上限是一棵满二叉树，所以结点总数N(4)N=4*(L-1)-15由线段树的定义及性质（6）知，访问区间范围为[1,L]的线段树上任一结点，最多需要访问21logL（即树深度）个结点，所以它的时间复杂度应该是2()logn。第二章线段树的建立2.1线段树结点定义对于一般线段树而言，可以用数组来表示，一个结点应该包含以下信息：(1).该结点所代表的区间，包括左边界与右边界(2).该结点的附带信息而对其孩子结点的信息，可以不作说明，解释可参考本文2.2节由此可见对于一个结点来讲，其包含信息还是比较多的，所以用结构体来存储一个结点的信息，是比较合理的选择。线段树结点的一般表示如下：structNODE{intleft,right;//结点所代表区间的左边界与右边界intvalue;//结点的附带信息};对于一些有特殊需要的题目，上述线段树结点的设计已经不能满足解题要求。所以，一些链式结构的线段树的结点就应运而生，相对用数组表示的线段树来讲，链式存储的线段树的结点应该包含其左右孩子的信息