WC2011-线段树-曹钦翔.ppt

《WC2011-线段树-曹钦翔.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线段树北京大学哲学系曹钦翔2011年1月22日线段树北京大学哲学系曹钦翔目录1.模块化编程2.从线段树高级功能到线段树结构的设计3.从OI问题到线段树功能的设计2011年1月22日线段树北京大学哲学系曹钦翔1.1线段树基本问题有一个长为n的数列（输入），维护m次操作，每次操作是以下两种之一：(1)修改数列中的一个数(2)求数列中某连续一段的最小值解决思路：存储不变化的整体信息减少冗余操作线段树的核心思路！2011年1月22日线段树北京大学哲学系曹钦翔1.2线段树的结构n=8的结构：n=5的结构：2011年1月22日线段树北京大学哲学系曹钦翔结构要点根节点为：min[1]总层数h为O(logn

2、)的min[k]的左右儿子：min[2k]、min[2k+1]min[k]的父节点：min[k/2]a[k]对应的叶子节点：min[k+2h-1]2011年1月22日线段树北京大学哲学系曹钦翔单点修改操作修改a[2]Step1:快速查找叶子节点Step2:自底向上作修改2011年1月22日线段树北京大学哲学系曹钦翔段查询操作查询a[1]-a[4]的连续段Step1:快速查找叶子节点Step2:开区间代替闭区间Step3:自底向上统计2011年1月22日线段树北京大学哲学系曹钦翔1.3段修改操作的问题有一个长为n的数列（输入）a[1],a[2]…a[n]，有m次操作，每次操作是以下两种之一：(

3、1)将数列中的一段a[l]…a[r]全部改成常数C(2)询问某一项a[i]当前的值段修改的应对：整体修改标签2011年1月22日线段树北京大学哲学系曹钦翔单点查询操作查询a[5]Step1:快速查找叶子节点Step2:自顶向下传递整体修改信息Step3:节点上的修改信息就是询问的答案2011年1月22日线段树北京大学哲学系曹钦翔段修改操作Step1:快速查找叶子节点Step2:开区间代替闭区间Step3:自顶向下传递整体修改信息Step4:自底向上添加整体修改信息Step5:自底向上从新统计统计信息2011年1月22日线段树北京大学哲学系曹钦翔段查询操作2Step1:快速查找叶子节点Step

4、2:开区间代替闭区间Step3:自顶向下传递整体修改信息Step4:自底向上统计答案2011年1月22日线段树北京大学哲学系曹钦翔1.5模式化的程序Step1:快速查找叶子节点Step2:开区间代替闭区间（限于段操作）Step3:自顶向下传递整体修改信息Step4:自底向上统计（段查询）/修改（段修改）2011年1月22日线段树北京大学哲学系曹钦翔1.5模式化的程序对区间a[3]-a[5]操作2011年1月22日线段树北京大学哲学系曹钦翔2.线段树结构的设计模式化之外的部分：1.SavingData的设计2.RefreshInformation的设计3.SavingData的和并运算Savi

5、ng_Typeoperator+(Saving_Typea,Saving_Typeb)4.SavingData被RefreshInformation所修改Saving_Typeoperator*(Saving_Typea,RefInf_Typeb)5.RefreshInformation的连接运算RefInf_Typeoperator*(RefInf_Typea,RefInf_Typeb)…………………………2011年1月22日线段树北京大学哲学系曹钦翔例题2.1问题描述有一个平面连轴支架，包含n根棍子，相邻两根有一个连接点。第一根有一端（不连第二根的那端）固定在(0,0)。维护三个操作：(

6、1)绕某一连接点旋转（这个点把所有棍子分成两部分，他们旋转时分别是一个整体）(2)某根棍子拉长或缩短(3)询问某连接点坐标2011年1月22日线段树北京大学哲学系曹钦翔例题2.2问题描述有一个集合A，初始值时，维护以下操作：(1)与某区间取并(2)与某区间取交(3)与某区间取对称差(4)减去某区间2011年1月22日线段树北京大学哲学系曹钦翔例题2.2问题描述(5)被某区间减(6)取补(7)询问某数是否在该集合内在程序最后，以区间的并的形式输出该集合2011年1月22日线段树北京大学哲学系曹钦翔例题2.3问题描述输入一个长为n的数列，维护m个操作，操作分为三类：(1)某连续段一起加上一个常数

7、(2)询问某一段的所有数的两两乘积的和(3)询问某一段的所有相邻两数乘积的和2011年1月22日线段树北京大学哲学系曹钦翔例题2.4问题描述输入两个个长为n的数列a[i],b[i]，维护m个操作，操作分为三类：(1)对于某一连续段将其中的b[i]加到a[i]上(2)对于某一连续段将其中的a[i]加到b[i]上(3)询问某一段中所有的a[i]b[i]的和2011年1月22日线段树北京大学哲学系曹钦翔例题2.5问