《线段树的应用》由会员分享，可在线阅读，更多相关《线段树的应用（25页珍藏版）》请在金锄头文库上搜索。
1、线段树的应用引例 数列操作v假设有一列数Ai(1in)，支持如下两种操作：将Ak的值加D。（k, D是输入的数）输出As+As+1+At。（s, t都是输入的数，ST）v v输入：第一行一个整数n，v 第二行为n个整数，表示Ai的初始值。v 第三行为一个整数m，表示操作数v 下接m行，每行描述一个操作，有如下两种情况：v ADD k d (表示将Ak加d，11 : a, (a+b) div 2为 T的左儿子；v (a+b) div 2,b为T 的右儿子。 v若L=1 : T为叶子节点。表示区间1, 10的线段树样例： 1,10 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3
2、 3,4 4,5 5,6 6,7 7,8 8,10 8,9 9,10 引例 线段树的建立v我们知道，对于长度为n的线段建立的线段 树，至多只有nlogn个节点，故建立线段树 的复杂度是O(nlogn)Procedure MakeTree(a,b) Var Now:Longint Begintot tot + 1 Now totTreeNow.a a TreeNow.b bIf a +1 then Insert(Treev.Right) End例一 线段树的插入、删除(2)v删除线段c,d的操作，只需要将Treev.Cover Treev.Cover + 1 改成Treev.Cover Tree
3、v.Cover 1 即可。v与引例中计算SUM的过程段类似地分析，不难得 到线段树中插入和删除线段的时间复杂度都是 O(logn)例一 Picture(IOI98)v回到原问题，首先我们考虑纵向的离散区间。我们从左到右依次扫描每个离散区间。如上，考察第一个离散区间。蓝色的线段显然要算入最 后的“轮廓长度”。我们把蓝色线段插入线段树。例一 Picture(IOI98)在第二个区间我们加 入了另一个矩形的左边界 ，如右图蓝色线段。把这 条线段加入到线段树中。 但是用圆形圈起来的部分 不应该算到“轮廓长度”里 面去。究其原因，因为圆 形圈起来的部分和之前已 经插入的线段重合了。也 就是说每插入一条新
4、线线段 ，只有不和之前已插入线线 段重合的部分才应该应该 被算 到“轮轮廓长长度”里面去。接着考察第三个区间， 我们面对的是一个矩形的右 边界，因此我们要把它对应 的绿色线段从树中删除。 右图的蓝色线段中，圆 形圈起来的部分不算到轮廓里 面去。究其原因，是因为这 个部分和除被删除线段之外 的线段有交集。例一 Picture(IOI98)例一 Picture(IOI98)v综合前面的分析，我们得到：v每次插入/删除操作之前，线段树中线段覆盖的总 长度是X；之后的总长度是Y。那么应该算入轮廓 的长度就是|X-Y|。v关于如何计算“覆盖的总长度”，与引例中计算区间 和类似，这里不再赘述。v这样我们就
5、可以通过一遍扫描，计算出所有的纵 向轮廓长度。这是只需要把图旋转90度，就可以 用同样的方法计算横向轮廓的长度了。例一 Picture(IOI98)v由于每条矩形的边界线段只被扫描一 遍，而且扫描的时候进行的插入或删 除操作的时间复杂度是O(logn)v所以算法的总时间复杂度是O(nlogn) 。例二 Squarev给你一个n*n的方格棋盘，初始时每个格子 都是白色。现在要刷M次黑色或白色的油漆 。每次刷漆的区域都是一个平行棋盘边缘的 矩形区域。v输入n,M,以及每次刷漆的区域和颜色，输出 刷了M次之后棋盘上还有多少个棋格是白色 。例二 一维问题v首先我们从简单入手，考虑一维的问题。即 对于一
6、个长度为n的白色线段，对它进行M 次修改（每次更新某一子区域的颜色）。问 最后还剩下的白色区域有多长。v对于这个问题，很容易想到建立一棵线段树 的模型。例二 一维问题的解决v对于这个问题，在线段树中增添一个域 Treev.white，记录该区间当前有多少部分 是白色。然后再进行线段的插入和颜色统计 。单次操作的复杂度都是O(logn)v算法的总时间复杂度是O(Mlogn)例二 Squarev那么原来的问题怎么解决呢？v为了适应原问题的特殊性，我们需要把线段 树进行调整，即首先在横坐标上建立线段树 ，它的每个节点是一棵建立在纵坐标上的线 段树（即树中有树）。v我们称之为二维线段树。例二 Square如下图就是一棵二维线段树：例二 Squarev二维线段树的操作完全类同于一维线段树。v二维线段树上单次的插入（删除、查找、改值等 ）操作的复杂度都是O(log2n)。v将二维线段数应用到原问题当中，总的时间复杂 度是O(Mlog2n)v还有一种结构比较简单的二维线段树，就是每个 节点不再是区间，而是一个子平面。大家可以自 己去实现一下，比较一下这两种构造方法的异同 。
