线段树应用PPT课件

线段树的应用 线段树的定义线段树是一棵二叉树，记为线段树是一棵二叉树，记为T(T(a a,b b)，参数，参数a a,b b表示区间表示区间 a a,b b，其中，其中b b-a a称为区间的长度，记为称为区间的长度，记为L L。线段树线段树T(T(a a,b b)也可递归定义为：也可递归定义为：若若L L1:a,(a+b)div 21:a,(a+b)div 2为为 T T的左儿子；的左儿子；(a+b)div 2,b (a+b)div 2,b为为T T 的右儿子。的右儿子。若若L L=1:T=1:T为叶子节点。为叶子节点。表示区间表示区间1,101,10的线段树样例：的线段树样例：1,10 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,10 8,9 9,10 线段树的特征 n n定理二：线段树把区间上的任意一条线段定理二：线段树把区间上的任意一条线段都分成不超过都分成不超过2logL条线段。条线段。n n这些结论为线段树能在这些结论为线段树能在O(logO(logL L)的时间内完的时间内完成一条线段的插入、删除、查找等工作，成一条线段的插入、删除、查找等工作，提供了理论依据提供了理论依据 n n定理一：线段树的深度不超过定理一：线段树的深度不超过logL。线段树的基本操作n n插入一条线段：每个节点增加一个变量记录该节插入一条线段：每个节点增加一个变量记录该节点被插入所有线段覆盖的次数，自根节点往下，点被插入所有线段覆盖的次数，自根节点往下，直到一个被线段完全覆盖的节点。直到一个被线段完全覆盖的节点。节点被插入的线段覆盖记录变量加1，儿子不再处理节点与插入线段不相干该节点及儿子都不作处理相干但不被覆盖把线段分别插入它的两个儿子n n删除一条插入过的线段，与插入操作是一致的。删除一条插入过的线段，与插入操作是一致的。n n查找一个区间内线段的总长度。每个节点增加一查找一个区间内线段的总长度。每个节点增加一个变量记录该区间内线段的总长度，并在插入和个变量记录该区间内线段的总长度，并在插入和删除后维护相关节点的这个变量：删除后维护相关节点的这个变量：儿子区间内的线段长度儿子区间内的线段长度+覆盖本区间的线段长度覆盖本区间的线段长度例1：蛇（SGU 128）n n在平面上有在平面上有N N个点，现在要用一些线段将它们连起来，使个点，现在要用一些线段将它们连起来，使其满足以下要求：其满足以下要求：1 1 这些线段必须闭合这些线段必须闭合2 2 线段的端点只能是这线段的端点只能是这N N个点。个点。3 3 交于一点的两条线段成交于一点的两条线段成9090度角度角4 4 线段都必须平行于线段都必须平行于X X轴或轴或Y Y轴轴5 5 所有线段除了在这所有线段除了在这N N个点外不相交个点外不相交6 6 所有线段的长度之和必须最短所有线段的长度之和必须最短n n如果存在这样的线段，则输出最小长度，否则输出如果存在这样的线段，则输出最小长度，否则输出0 0。XY【问题分析】【问题分析】n n所求的图形是以题目所给的所求的图形是以题目所给的N N个点为顶点的多边个点为顶点的多边形。每条边要和形。每条边要和X X轴或轴或Y Y轴平行。每个顶点与一轴平行。每个顶点与一条平行于条平行于X X轴和一条平行于轴和一条平行于Y Y轴的线段相连。轴的线段相连。XYP1P2P3P4P5P6P7P8n n将所有点排序后发现，在同一水平线的点中，设将所有点排序后发现，在同一水平线的点中，设为为P1P1，P2P2，P3P3，P4P4PnPn，P1P1必须连它右边的必须连它右边的点点P2P2，P3P3只能连只能连P4P4，P5P5连连P6P6，同垂直线同垂直线上的点也是如此。上的点也是如此。n n如果有解，解是唯一的，那么最小长度的问题就如果有解，解是唯一的，那么最小长度的问题就解决了。解决了。不相连不合法不自交合法自交不合法n n由于解是唯一，所以关键在于判断由上述方法构由于解是唯一，所以关键在于判断由上述方法构出的图形是否合法出的图形是否合法满足线段不自交：满足线段不自交：【问题分析】【问题分析】n n如图，两条线段在内部相交，则必须满足x1xx2 和 y1yy2。【问题解法】【问题解法】n n将所有线段按将所有线段按X X轴坐标排序，每条平行于轴坐标排序，每条平行于Y Y轴的轴的线段和每个平行于线段和每个平行于X X轴线段的端点称为一个事件轴线段的端点称为一个事件n n由于这题的区间性很明显，可以用线段树来解决。由于这题的区间性很明显，可以用线段树来解决。n n本题要注意的是，线段在端点重合不算自交，所以X轴坐标相同时，事件的顺序要恰当处理。n n将Y轴代表的区间建成线段树，并且每个节点记录它的区间内插入的点数。按顺序，扫描所有事件：如果遇到平行于X轴线段的左端点，则插入到线段树中，遇到右端点，则从线段树中删除。如果遇到平行于Y轴的线段，则在线段树中查找。n n将轴坐标离散后，每次插入、删除、查找的复杂度是(logn)级别的，由于所有线段数量是(n)级别的，所以整题的复杂度是(nlogn)级别。n n思考：本题删除的点与插入的点一一对应，所以删除实现很方便。如果删除的线段不一定插入过该怎么办？例2：空心长方体（POI99 Cuboid）n n在一个三维正坐标系中，存在N(NQx PyQy PzQzn n体积最大的长方体，其P点任意轴的坐标，都与N个点中的一个相同或者和边界相同。【问题分析】【问题分析】n n在已经确定P的X坐标情况下,将所有点的y坐标排序，得到序列y1，y2，y3。maxi记录P的Y轴坐标为yi时，Z轴坐标的最大取值，数组max的值是单调不增的。n n把所有点按X轴坐标排序，当P点的X坐标与第i个点相同时，第i及第i以后的点都不可能被P包含了。yiQy把max看成一个区间yiQymaxjzn n可以看出每增加一个点的限制，需要修改的是一个区间，要高效的进行区间操作就可以用到线段树。【问题分析】【问题分析】n n从小到大枚举P点的X坐标，这个过程中要不断维护数组max。因为P的 X坐标由第i个点的变成第i+1个点的，第i 个点的坐标就会增加对数组max 的限制。n n考虑第i个点Q(x,y,z)增加对数组的限制maxjz【问题解法】【问题解法】n n建立关于数组建立关于数组maxmax的线段树，每增加一个节点的限制，就的线段树，每增加一个节点的限制，就相当于修改线段树中的一个区间内的值相当于修改线段树中的一个区间内的值n n修改的区间如果包含节点修改的区间如果包含节点V V表示的区间，那么表示的区间，那么V V及及V V的儿子的儿子都要修改，但是我们只要修改都要修改，但是我们只要修改V V：由于：由于V V的区间内的值相同，的区间内的值相同，将子树将子树V V收缩成一个叶子节点。收缩成一个叶子节点。n n相反的，如果修改的区间不包含节点相反的，如果修改的区间不包含节点V V，而，而V V又已经被收缩又已经被收缩成一个叶子节点，那么我们将这个叶子节点释放出两个儿成一个叶子节点，那么我们将这个叶子节点释放出两个儿子。子。n n线段树中，每个节点要记录其表示的区间内maxi*yi的最大值，并且在数组被修改时，维护这个最大值。根节点的最大值与P点当前X坐标相乘,就是当前最大体积。【问题解法】【问题解法】n n由于利用子树收缩的方法，离散后，每次修改的节点数是O(logn)级别，相关的维护也是这个级别，所以本题的复杂度为O(nlogn)。n n总结这题的成功之处：不把线段树死板的按看成固定的，而是抓住线段树叶子节点的本质区间内的各种数据是单一，根据情况把子树收缩为叶子或让叶子释放出儿子，从而避免重复的操作。例3：战场统计系统【问题描述】【问题描述】人类与外星人之间的战争已趋于白热化请你尽快设计出这人类与外星人之间的战争已趋于白热化请你尽快设计出这样一套系统。这套系统需要具备能够处理如下样一套系统。这套系统需要具备能够处理如下2 2类信息的能类信息的能力：力：n n外星人向外星人向x1x1，x2x2内的每个位置增援一支防御力为内的每个位置增援一支防御力为v v的部队。的部队。n n人类使用超级武器对人类使用超级武器对x1x1，x2x2内的所有位置进行一次攻击内的所有位置进行一次攻击力为力为v v的打击。系统需要返回在这次攻击中被消灭的外星人的打击。系统需要返回在这次攻击中被消灭的外星人个数。个数。n n注：防御力为注：防御力为i i的外星人部队由的外星人部队由i i个外星人组成，其中第个外星人组成，其中第j j个外个外星人的防御力为星人的防御力为j j。数据范围：。数据范围：1=x1=x2=1000,v=10001=x1=x2=1000,v=1000；信息总数；信息总数m=2000m=2000。【问题分析】【问题分析】n n把两类信息抽象化：把两类信息抽象化：TTx,yx,y 表示单位区间表示单位区间 x,xx,x 上防御力为上防御力为y y的部队数目，如果在的部队数目，如果在x1x1，x2x2增加防御力为增加防御力为v v的部队，就的部队，就是在这个二维数组内，添加一个是在这个二维数组内，添加一个 x x1,1,x x21,21,v v 的矩形的矩形;要要使用一次武器就相当于查找一个矩形使用一次武器就相当于查找一个矩形 x x1,1,x x2 1,2 1,v v 内的内的部队数目，并将此矩形内的所有部队删除。部队数目，并将此矩形内的所有部队删除。YXv1v2x1x3x2x4YX1 2 3 4 n n首先可以考虑在一维上优化，在每个单位区间x,x上，分别用一棵线段树记录各种防御力的部队数。【问题分析】【问题分析】n n如果采用最简单的方法：对矩形内的每个点进行操作，复杂度高达O(m*n*v)。n n插入一个矩形x1,x21,v，就变成了执行x2-x1+1次在线段树上插入线段1,v的操作，这和一般插入是一样的。n n统计一个矩形内的部队数目并删除该矩形统计一个矩形内的部队数目并删除该矩形 x1,x2x1,x21,v1,v 内的部队，也是要在每个单位区间内的部队，也是要在每个单位区间执行一次操作。如果执行一次操作。如果V V不被不被 1,v1,v 包含，则要把本包含，则要把本来覆盖它区间的分配给两个儿子。来覆盖它区间的分配给两个儿子。【问题解法】【问题解法】将原来覆盖该区间的分配给两个儿子要删除的子树收缩成一个叶子节点一个叶子节点释放出两个儿子n n而如果要删除而如果要删除V V区间，那么可以用前面的收缩子树区间，那么可以用前面的收缩子树 的方法，如果在插入时遇到叶子节点同样运用前的方法，如果在插入时遇到叶子节点同样运用前面的方法释放出两个儿子节点。面的方法释放出两个儿子节点。n n优化后每次删除、统计、插入的复杂度都是O(n*logv)，所以总的复杂度降为O(m*n*logv);n n 由于这是个二维的区间，不妨将整个二维的区间建成类似线段树的面积树：n n假设整个二维区间是1.2k1.2k，递归定义一棵树T：1 T的根节点为整个二维区间。2 区间x,xy,y为叶子节点 3 儿子的划分:【问题分析【问题分析】n n建立面积树后，任意一个矩形在树中，都被划分为不超过O(2k)块区域，仿造线段树的方法进行插入、查找、和删除，就可以把本题复杂度降为O(m*(n+v)总结用线段树解题的方法n n根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等。n n树的每个节点根据题目所需，设置变量记录要求的值。n n用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。n n在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。谢谢！