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