线段树及其应用(朱全民)

引例数列操作假设有一列数{Ai}(1≤i≤n)，支持如下两种操作：将Ak的值加D。（k,D是输入的数）输出As+As+1+…+At。（s,t都是输入的数，S≤T）输入：第一行一个整数n，第二行为n个整数，表示{Ai}的初始值。第三行为一个整数m，表示操作数下接m行，每行描述一个操作，有如下两种情况：ADDkd(表示将Ak加d，1=k=n，d为整数)SUMst（表示输出As+…+At）输出：对于每一个SUM提问，输出结果如果按题目要求直接模拟：每一个ADD操作的复杂度是O(1)每一个SUM操作的复杂度是O(N)可见对于M次SUM询问，复杂度是O(NM)有没有更好的方法呢？这里我们提出一种称之为线段树的数据结构。引例数列操作引例线段树的定义线段树是一棵二叉树，记为T(a,b)，参数a,b表示区间[a,b]，其中b-a称为区间的长度，记为L。线段树T(a,b)也可递归定义为：若L1:[a,(a+b)div2]为T的左儿子；[(a+b)div2,b]为T的右儿子。若L=1:T为叶子节点。表示区间[1,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的线段建立的线段树，至多只有nlogn个节点，故建立线段树的复杂度是O(nlogn)ProcedureMakeTree(a,b)VarNow:LongintBegintot←tot+1Now←totTree[Now].a←aTree[Now].b←bIfa+1bthenTree[Now].Left←tot+1MakeTree(a,)Tree[Now].Right←tot+1MakeTree(,b)End2/)(ba2/)(ba引例回到原问题我们用线段树来维护序列。给线段树的每个节点增加一个域Tree[i].S，表示该区间内所有值的和。对于ADDkd操作，只需要从根节点开始遍历线段树中每个包含了k的区间节点，然后修改S域。由于这样的区间至多只有logn个，所以一次ADD操作的复杂度是O(logn)引例SUM操作对于待计算的区间[s,t]：Functiongetsum(v):integer;if(s=Tree[v].a)and(Tree[v].b=t)thengetsum:=Tree[v].Selsebegintot:=0;if[s,t]和Tree[v].Left表示的区间相交thentot:=tot+getsum(Tree[v].Left);if[s,t]和Tree[v].Right表示的区间相交thentot:=tot+getsum(Tree[v].Right);getsum:=totend;我们不难发现这个过程中所遍历到的区间数（节点数）和线段树的深度同阶，因此时间复杂度是O(logn)引例问题的解决综上，M次操作的时间复杂度为O(Mlogn)通过引入线段树的数据结构，虽然ADD操作的复杂度提高到了O(logn)。但SUM操作变得更快(O(logn))。从而也使得算法在大数据处理上更加高效。例一Picture(IOI98)墙上贴了一些矩形的张贴画和照片。他们的边都是垂直或者水平的。每个矩形可以部分后者全部被其他的矩形覆盖。把这些矩形看作一个整体，他们的边界长度就是他们的轮廓长度。所有顶点坐标都是整数。任务：写一个程序计算轮廓长度。下面的图1是一个7个矩形的例子：图1：七个矩形这些矩形的轮廓如图2所示图2：图1中7个矩形的轮廓例一Picture(IOI98)预处理：如右图所示，用2n条横线与2n条纵线将坐标平面重新进行划分。定义新的坐标轴，并记录每一个“元线段”的长度。这样就只剩下了2n*2n个坐标点，便于今后的计算。离散化，将2n条矩形的横边和2n条纵边取出来，分别计算DABC例一Picture(IOI98)做完预处理之后，如果直接计算，不难想到O(n2)的算法。事实上，利用线段树我们可以设计出一个时间复杂度为O(nlogn)的高效算法。在分析算法之前，我们先来看看线段树上插入和删除线段的操作。例一线段树的插入、删除(1)增加一个Tree[i].Cover域，记录该区间（线段）被覆盖的次数。则在线段树中插入线段[c,d]的代码段如下：ProcedureInsert(v)BeginIf(cTree[v].a)and(Tree[v].bd)thenTree[v].Cover←Tree[v].Cover+1ElseIfcthenInsert(Tree[v].Left)IfdthenInsert(Tree[v].Right)End2/)].[].[(bvTreeavTree2/)].[].[(bvTreeavTree例一线段树的插入、删除(2)删除线段[c,d]的操作，只需要将Tree[v].Cover←Tree[v].Cover+1改成Tree[v].Cover←Tree[v].Cover–1即可。与引例中计算SUM的过程段类似地分析，不难得到线段树中插入和删除线段的时间复杂度都是O(logn)例一Picture(IOI98)回到原问题，首先我们考虑纵向的离散区间。我们从左到右依次扫描每个离散区间。如上，考察第一个离散区间。蓝色的线段显然要算入最后的“轮廓长度”。我们把蓝色线段插入线段树。例一Picture(IOI98)在第二个区间我们加入了另一个矩形的左边界，如右图蓝色线段。把这条线段加入到线段树中。但是用圆形圈起来的部分不应该算到“轮廓长度”里面去。究其原因，因为圆形圈起来的部分和之前已经插入的线段重合了。也就是说每插入一条新线段，只有不和之前已插入线段重合的部分才应该被算到“轮廓长度”里面去。接着考察第三个区间，我们面对的是一个矩形的右边界，因此我们要把它对应的绿色线段从树中删除。右图的蓝色线段中，圆形圈起来的部分不算到轮廓里面去。究其原因，是因为这个部分和除被删除线段之外的线段有交集。例一Picture(IOI98)例一Picture(IOI98)综合前面的分析，我们得到：每次插入/删除操作之前，线段树中线段覆盖的总长度是X；之后的总长度是Y。那么应该算入轮廓的长度就是|X-Y|。关于如何计算“覆盖的总长度”，与引例中计算区间和类似，这里不再赘述。这样我们就可以通过一遍扫描，计算出所有的纵向轮廓长度。这是只需要把图旋转90度，就可以用同样的方法计算横向轮廓的长度了。例一Picture(IOI98)由于每条矩形的边界线段只被扫描一遍，而且扫描的时候进行的插入或删除操作的时间复杂度是O(logn)所以算法的总时间复杂度是O(nlogn)。例二Square给你一个n*n的方格棋盘，初始时每个格子都是白色。现在要刷M次黑色或白色的油漆。每次刷漆的区域都是一个平行棋盘边缘的矩形区域。输入n,M,以及每次刷漆的区域和颜色，输出刷了M次之后棋盘上还有多少个棋格是白色。例二一维问题首先我们从简单入手，考虑一维的问题。即对于一个长度为n的白色线段，对它进行M次修改（每次更新某一子区域的颜色）。问最后还剩下的白色区域有多长。对于这个问题，很容易想到建立一棵线段树的模型。例二一维问题的解决对于这个问题，在线段树中增添一个域Tree[v].white，记录该区间当前有多少部分是白色。然后再进行线段的插入和颜色统计。单次操作的复杂度都是O(logn)算法的总时间复杂度是O(Mlogn)例二Square那么原来的问题怎么解决呢？为了适应原问题的特殊性，我们需要把线段树进行调整，即首先在横坐标上建立线段树，它的每个节点是一棵建立在纵坐标上的线段树（即树中有树）。我们称之为二维线段树。例二Square如下图就是一棵二维线段树：15133512233445151335122334451513351223344515133512233445151335122334451513351223344515133512233445[1,5][1,3][3,5][1,2][2,3][3,4][4,5]例二Square二维线段树的操作完全类同于一维线段树。二维线段树上单次的插入（删除、查找、改值等）操作的复杂度都是O(log2n)。将二维线段数应用到原问题当中，总的时间复杂度是O(Mlog2n)还有一种结构比较简单的二维线段树，就是每个节点不再是区间，而是一个子平面。大家可以自己去实现一下，比较一下这两种构造方法的异同。