WC2011-线段树-曹钦翔.ppt

2011年1月22日,线段树 北京大学哲学系 曹钦翔,线段树,北京大学哲学系 曹钦翔,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日,线段树 北京大学哲学系 曹钦翔,结构要点,根节点为：min1 总层数h为O(logn)的 mink的左右儿子：min2k、min2k+1 mink的父节点：mink/2 ak对应的叶子节点：mink+2h-1,2011年1月22日,线段树 北京大学哲学系 曹钦翔,单点修改操作,修改a2,Step 1: 快速查找叶子节点,Step 2: 自底向上作修改,2011年1月22日,线段树 北京大学哲学系 曹钦翔,段查询操作,查询a1-a4的连续段,Step 1: 快速查找叶子节点,Step 2: 开区间代替闭区间,Step 3: 自底向上统计,2011年1月22日,线段树 北京大学哲学系 曹钦翔,1.3 段修改操作的问题,有一个长为n的数列（输入）a1,a2an，有m次操作，每次操作是以下两种之一： (1)将数列中的一段alar全部改成常数C (2)询问某一项ai当前的值 段修改的应对：整体修改标签,2011年1月22日,线段树 北京大学哲学系 曹钦翔,单点查询操作,查询a5,Step 1: 快速查找叶子节点,Step 2: 自顶向下传递整体修改信息,Step 3: 节点上的修改信息就是询问的答案,2011年1月22日,线段树 北京大学哲学系 曹钦翔,段修改操作,Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间 Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上添加整体修改信息 Step 5: 自底向上从新统计统计信息,2011年1月22日,线段树 北京大学哲学系 曹钦翔,段查询操作2,Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间 Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上统计答案,2011年1月22日,线段树 北京大学哲学系 曹钦翔,1.5 模式化的程序,Step 1: 快速查找叶子节点 Step 2: 开区间代替闭区间（限于段操作） Step 3: 自顶向下传递整体修改信息 Step 4: 自底向上统计（段查询）/修改（段修改）,2011年1月22日,线段树 北京大学哲学系 曹钦翔,1.5 模式化的程序,对区间a3-a5操作,2011年1月22日,线段树 北京大学哲学系 曹钦翔,2. 线段树结构的设计,模式化之外的部分： 1. Saving Data的设计,2. Refresh Information的设计,3. Saving Data 的和并运算 Saving_Type operator+(Saving_Type a, Saving_Type b),4. Saving Data 被 Refresh Information 所修改 Saving_Type operator*(Saving_Type a, RefInf_Type b),5. Refresh Information 的连接运算 RefInf_Type operator*(RefInf_Type a, RefInf_Type b), , ,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.1,问题描述 有一个平面连轴支架，包含n根棍子，相邻两根有一个连接点。第一根有一端（不连第二根的那端）固定在(0,0)。维护三个操作： (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)某连续段一起加上一个常数 (2)询问某一段的所有数的两两乘积的和 (3)询问某一段的所有相邻两数乘积的和,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.4,问题描述 输入两个个长为n的数列ai,bi，维护m个操作，操作分为三类： (1)对于某一连续段将其中的bi加到ai上 (2)对于某一连续段将其中的ai加到bi上 (3)询问某一段中所有的aibi的和,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.5,问题描述 输入长度为n的数列ai。维护m次操作，每次操作可以： (1)alar每一项都加一个常数C (2)求F al +F al+1 +F ar mod 10001的余数 (3)求F al +F al+1 +F ar mod 10001的余数 其中Fi表示斐波那契数列。即F0=F1=1，Fn+2=Fn+1+Fn。（C=1011）,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.6,问题描述 输入一个状态集大小不超过10的AC自动机，s是一个字符串，即AC自动机的输入。维护m个操作，操作分为两类： (1)修改s的一个字符 (2)询问s对应的输出,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.7,问题描述 平面上放置了一个正四面体，初始时底面是A面，且此时A面中心在原点，“向前”方向为Y轴正方向。可以对该四面体执行指令左转（L）、右转（R）、后转（B）。s是一个输入的指令串。维护m个操作，操作分为三类： (1)修改s的一个字符 (2)询问s执行结束后，地面中心距离原点的距离 (3)询问某段时间内，A成为底面的次数,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.7,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.8,问题描述 有一个2*n的点阵，平行于坐标轴的方向上相邻的点之间可以连边，维护以下操作： (1)在某两点之间连边（可以连边的话） (2)拆除某条边 (3)询问某两点是否连通,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.8,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 2.9,问题描述 白雪公主和n个小矮人住在森林里，当小矮人们排成一排向外走的时候，每个人头上都戴了一顶帽子，每顶帽子有一种颜色。这时候白雪公主给他们拍照片，共拍了m张，每张照片包括了队伍中连续的几个小矮人。 白雪公主认为，如果一张照片中某种颜色的帽子超过一半（共有s人的话，严格大于s/2人），她就认为这张照片很“好看”。输入每个小矮人的帽子的颜色，每张照片的小矮人的范围第li人到第ri人，问哪些照片是特别“好看”的，并对于每张“好看”的照片输出其中最多的帽子颜色。,2011年1月22日,线段树 北京大学哲学系 曹钦翔,3. 线段树操作的设计,设计线段树的坐标轴 设计有顺序的操作 将操作转化为线段树的操作,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 3.1,问题描述 平面上有n个边平行于坐标轴的矩形。输入他们的位置，问：恰好被覆盖到奇数次的面积是多少？被覆盖过至少一次的总面积是多少？,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 3.2,问题描述 A是一个集合，它的元素是一些开区间。若A中每个元素有一个权值，离线回答下面的所有询问： 对于输入的开区间x=(lx,rx) (1)A中，与x左交的元素的权值的最小值 (2)A中，包含x的元素的权值的最小值 (3)A中，被x包含的元素的权值的最小值,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 3.3,问题描述 输入一个n个点的边有权的有根树。维护m个操作，操作共有如下两类： (1)将某子树中的所有边权都增加一个常数C (2)求某两点之间路径上的边权的平方和,2011年1月22日,线段树 北京大学哲学系 曹钦翔,例题 3.4,问题描述 某大厦有一会议室可以为企业或者单位提供会议场地