线段树及其应用.ppt

《线段树及其应用.ppt》由会员分享，可在线阅读，更多相关《线段树及其应用.ppt（59页珍藏版）》请在三一办公上搜索。

1、线段树及其应用,江苏省华罗庚中学 xxx,为什么要用线段树？,例1：有M个数排成一列，初始值全为0，然后做N次操作，每次我们可以进行如下操作：（1）将指定区间的每个数加上一个值；（2）将指定区间的所有数置成一个值；（3）询问一个区间上的最小值、最大值、所有数的和。,为什么要用线段树？,一般的模拟算法：用一张线性表表示整个数列，每次执行前两个操作的时候，将对应区间里的数值逐一进行修改，执行第三个操作的时候，线性扫描询问区间，求出三个统计值，每次维护的时间复杂度O(m)，整体的时间复杂度O(mn)。,为什么要用线段树？,readln(m,n);for i:=1 to n dobegin read(

2、t);if t=1/指定区间加上一个值 then begin readln(left,right,x);for j:=left to right do aj:=aj+x;end;,if t=2/指定区间置成一个值then begin readln(left,right,x);for j:=left to right do aj:=x;end;,为什么要用线段树？,if t=3/询问一个区间的最小值、最大值、和then begin readln(left,right);min:=aleft;max:=aleft;sum:=aleft;for j:=left+1 to right do begin

3、 if ajmax then max:=aj;sum:=sum+aj;end;writeln(min,max,sum);end;,为什么要用线段树？,机器配置：Pentium 1.3G 512M,时间复杂度是线性的！,为什么要用线段树？,当m、n的值比较大时，这个算法就太低效了。其低效的原因主要是我们在每一次操作中都是针对每个元素进行维护的，而这里我们进行的操作都是针对一个区间进行操作的。假如设计一种数据结构，能够直接维护所需处理的区间，那么就能更加有效地解决这个问题。,线段树（区间树）,线段树的结构,定义1：长度为1的线段称为元线段。定义2：一棵树被称为线段树，当且仅当这棵树满足如下条件：（

4、1）该树是一棵二叉树；（2）树中的每一个结点都对应一条线段a,b；（3）树中的结点是叶子结点，当且仅当它所代表的线段是元线段；（4）树中非叶子结点都有左右两棵子树，左子树树根对应线段a,(a+b)/2，右子树树根对应线段(a+b)/2,b。,线段树的结构,如T(1,10)的结构：,线段树的结构,常用的是需要对数列进行处理，将区间a,b分解为a,(a+b)/2，(a+b)/2+1,b，当a=b时表示为一个叶子结点，表示数列中的一个数。,线段树的性质,性质1：长度范围为1,L的一棵线段树的深度不超过log2(L-1)+1；性质2：线段树上的结点个数不超过2L个；性质3：线段树把区间上的任意一条线段

5、都分成不超过2log2L条线段。,线段树的存储方式,（1）链表实现：Node=TNode;TNode=record Left,Right:integer;LeftChild,RightChild:Node;end;（2）数组模拟链表：Left,Right,LeftChild,RightChild:array1.n of integer;（3）堆的结构：根节点为1，对于结点x，其左孩子为2x，右孩子为2x+1,线段树的基本操作及实现,线段树的构造procedure build(cur:Node;l,r:integer);begin cur.Left:=l;cur.Right:=r;if l=r

6、then begin cur.LeftChild:=nil;cur.RightChild:=nil;end else begin new(cur.LeftChild);new(cur.RightChild);build(cur.LeftChild,l,(l+r)div 2);build(cur.RightChild,(l+r)div 2+1,r);end;end;,线段树的基本操作及实现,线段树的查询procedure query(cur:Node;l,r:integer);var LC,RC:Node;begin LC:=cur.LeftChild;RC:=cur.RightChild;if

7、(l(cur.Left+cur.Right)div 2 then query(RC,l,r);end;end;,线段树的维护方法,对区间进行修改,对元素进行修改,设置为同一个数,统一加上一个数,修改,查询,区间的和,区间的最大值,区间的最小值,其它,线段树的维护方法,如果想要让线段树发挥实际的作用，必须在每个结点上维护额外的域来记录更多的信息。首先看一个引例的弱化版，假设每次修改操作只能对其中某个元素进行修改。在每个结点上额外维护3个域：max、min、sum，分别表示子树上的最大值、最小值和所有元素的和。,（1）对元素进行修改,procedure insert(cur:Node;x,num:

8、integer);var LC,RC:Node;begin LC:=cur.LeftChild;RC:=cur.RightChild;if cur.Left=cur.Right/对叶结点的处理 then begin cur.Min:=num;cur.Max:=num;cur.Sum:=num;end else begin if x(cur.Left+cur.Right)div 2 then insert(RC,x,num);cur.Sum:=LC.Sum+RC.Sum;/上推 if(LC.MaxRC.Max)then cur.Max:=LC.Max else cur.Max:=RC.Max;i

9、f(LC.MinRC.Min)then cur.Min:=LC.Min else cur.Min:=RC.Min;end;end;,（2）对区间进行查询,function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node;ret:integer;begin LC:=cur.LeftChild;RC:=cur.RightChild;ret:=0;if(l(cur.Left+cur.Right)div 2 then ret:=ret+querysum(RC,l,r);end;querysum:=ret;end;,（3）对区间修改（统一加上一

10、个数）,procedure update(cur:Node;l,r,delta:integer);var LC,RC:Node;/需要给每个区间增加一个变量deltabegin LC:=cur.LeftChild;RC:=cur.RightChild;if(l(cur.Left+cur.Right)div 2 then update(RC,l,r,delta);cur.Sum:=LC.Sum+LC.Delta*(LC.Right-LC.Left+1);cur.Sum:=cur.Sum+RC.Sum+/上推 RC.Delta*(RC.Right-RC.Left+1);end;end;,（4）对区

11、间查询,function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node;ret:integer;begin LC:=cur.LeftChild;RC:=cur.RightChild;ret:=0;if(l(cur.Left+cur.Right)div 2 then ret:=ret+querysum(RC,l,r);end;querysum:=ret;end;,（5）对区间修改（设置为同一个数）,procedure update(cur:Node;l,r,num:integer);var LC,RC:Node;begin LC:=c

12、ur.LeftChild;RC:=cur.RightChild;if cur.En/如果该区间已经是同一个值，将值下传给左右区间 then begin cur.sum:=(cur.right-cur.left+1)*cur.data;if LCnil then begin LC.Data:=cur.Data;LC.En:=true;end;if RCnil then begin RC.Data:=cur.Data;RC.En:=true;end;cur.En:=false;end;if(l(cur.Left+cur.Right)div 2 then update(RC,l,r,num);cur

13、.Sum:=calcsum(LC)+calcsum(RC);end;end;,function calcsum(cur:Node):integer;begin if cur.En then calcsum:=(cur.Right-cur.Left+1)*cur.Data else calcsum:=cur.Sum;end;,（6）对区间查询,function querysum(cur:Node;l,r:integer):integer;var LC,RC:Node;ret:integer;begin LC:=cur.LeftChild;RC:=cur.RightChild;ret:=0;if(

14、l(cur.Left+cur.Right)div 2 then ret:=ret+querysum(RC,l,r);end;querysum:=ret;end;,线段树的维护方法,线段树上的参数通常有两种维护方法：（1）一类参数表达了结点的性质，通常具有树型的递推性质，可以从下向上进行递推计算；（如sum,max,min）（2）一类参数表达了子树的性质，维护的时候可以先打上标记，在需要进一步访问其子结点的时候从上向下传递。（如delta,en）,线段树的维护方法,线段树上维护或者询问过程的一般过程：对于当前区间l,rif 达到某种边界条件（如叶结点或被整个区间完全包含）then 对维护或是询问

15、作相应处理else 将第二类标记传递下去(注意，在查询过程中也要处理)根据区间的关系，对两个孩子结点递归处理 利用递推关系，根据孩子结点的情况维护第一类信息,为什么要用线段树？,应用举例,例2、线段覆盖 在所有不大于30000的自然数范围内讨论一个问题：已知n条线段，把端点依次输入告诉你，然后有m（30000）个询问，每个询问输入一个点，要求这个点在多少条线段上出现过。,n=4 m=3线段：0,3 4,6 2,6 5,7询问：1，3，5,应用举例（线段覆盖）,可以直接对问题处理的区间建立线段树，在线段树上维护区间被覆盖的次数。将n条线段插入线段树，然后对于询问的每个点，直接查询被覆盖的次数即可

16、。,应用举例（线段覆盖）,这道题目完全可以不用线段树，将每个线段拆分成(L,+1)，(R+1,-1)的两个事件点，每个询问点也在对应坐标处加上一个询问的事件点，排序之后扫描就可以完成题目的询问。,Sum 1 1 2 2 2 3 3 1 0,+1,-1,-1,-1,+1,+1,+1,-1,应用举例（线段覆盖）,因为此问题是一个离线的问题，这是一个很简单的离线算法。线段树在处理在线问题的时候会更加有效，因为它维护了一个实时的信息。,应用举例,例3、售票系统 某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N

17、为车票张数，售票系统对该售票申请作出受理或不受理的决定。只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。1=C=60000，1=S=60000，1=R=60000，C为城市个数，S为列车上的座位数，R为所有售票申请总数。,应用举例（售票系统）,输入：4 6 41 4 21 3 22 4 31 2 3,输入：YESYESNONO,应用举例（售票系统）,可以把所有的车站顺次放在一个数轴上，在数轴上建立线段树，在线段树上维护区间的delta与max，每次判断一个售票申请是否可行就是查询区间上的最大值；每个插入一个售票请求，就是给一个区间上所有的元素加上购票数。,应用举例（

18、售票系统）,procedure build(cur:node;l,r:longint);begin cur.left:=l;cur.right:=r;if l=r then begin cur.leftchild:=nil;cur.rightchild:=nil;cur.delta:=0;cur.max:=0;end else begin new(cur.leftchild);new(cur.rightchild);build(cur.leftchild,l,(l+r)div 2);build(cur.rightchild,(l+r)div 2+1,r);end;end;,应用举例（售票系统）

19、,procedure update(cur:node;l,r,delta:longint);var lc,rc:node;begin lc:=cur.leftchild;rc:=cur.rightchild;if(l=cur.right)then begin cur.delta:=cur.delta+delta;cur.max:=cur.max+delta;end else begin if l(cur.left+cur.right)div 2 then update(rc,l,r,delta);if lc.maxrc.max then cur.max:=lc.max+cur.delta el

20、se cur.max:=rc.max+cur.delta;end;end;,function querymax(cur:node;l,r:longint):longint;var lc,rc:node;ret:longint;begin lc:=cur.leftchild;rc:=cur.rightchild;ret:=0;if(l(cur.left+cur.right)div 2 then if retquerymax(rc,l,r)+cur.delta then ret:=querymax(rc,l,r)+cur.delta;end;querymax:=ret;end;,Begin rea

21、dln(c,s,r);new(tree);build(tree,1,c);for i:=1 to r do begin readln(a,b,x);if querymax(tree,a,b-1)+xs then writeln(NO)else begin writeln(YES);update(tree,a,b-1,x);end;end;end.,算法改进,Function test(cur:node;l,r,x,remain:longint):boolean;var lc,rc:node;ret:boolean;begin lc:=cur.leftchild;rc:=cur.rightchi

22、ld;ret:=true;if(l=cur.right)then if cur.max+xremain then ret:=false else ret:=true else if(remain-cur.delta=0)then begin if l(cur.left+cur.right)div 2 then ret:=ret and test(rc,l,r,x,remain-cur.delta)end;test:=ret;end;,应用举例,例4、采矿 金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的

23、采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内。读入采金点的位置。计算最大的价值。数据范围：1=s,w=10000 1=s,w=10000-30000=x,y=30000,应用举例（采矿）,L1,L2,S,W,应用举例（采矿）,对于每一个点的纵坐标y，建立两个事件点(y,+1)，(y+w+1,-1)如5个点的纵坐标分别是(5,3,9,1,9),w=2得到10个事件点：(5,+1),(8,-1),(3,+1),(6,-1),(9,+1),(12,-1),(1,+1),(4,-1),(9,+1),(12,-1),然后从低到高求和，这些

24、和中最大的一个就是该带状区域中一个包含最多点数的矩形。,1 2 1 2 1 0+2 0,应用举例,例5、面积 平面上有若干个平行于坐标轴的矩形，它们可以相互重叠且每个矩形顶点的坐标都是整数，求这些矩形覆盖的总面积。输入：210 10 20 2015 15 25 30 输出：225,应用举例（面积）,10,15,20,25,应用举例（面积）,先把坐标离散化，然后从左往右扫描每一条垂直于X轴的线段，如果一条线段是矩形的左边界，则插入线段；如果是矩形的右边界，则删除线段。取得线段的长度即可得到当前离散条的面积。定义add、del两个数组分别记录每个矩形的左边界、右边界。输入：210 10 20 20

25、15 15 25 30,add10,1.h1=10;add10,1.h2=20;del20,1.h1=10;del20,1.h2=20;add15,1.h1=15;add15,1.h2=30;del25,1.h1=15;del25,1.h2=30;,应用举例（面积）,procedure build(cur:node;l,r:longint);begin cur.left:=l;cur.right:=r;if l+1=r then begin cur.leftchild:=nil;cur.rightchild:=nil;cur.delta:=0;cur.sum:=0;end else begin

26、 new(cur.leftchild);new(cur.rightchild);build(cur.leftchild,l,(l+r)div 2);build(cur.rightchild,(l+r)div 2,r);end;end;,procedure update(cur:node;l,r,t:longint);var lc,rc:node;begin lc:=cur.leftchild;rc:=cur.rightchild;if(l(cur.left+cur.right)div 2 then update(rc,l,r,t);if lc.delta0 then cur.sum:=lc.r

27、ight-lc.left else cur.sum:=lc.sum;if rc.delta0 then cur.sum:=cur.sum+rc.right-rc.left else cur.sum:=cur.sum+rc.sum;end;end;,应用举例（面积）,主程序：for i:=1 to 30000 dobegin addi:=nil;deli:=nil;end;readln(n);for i:=1 to n dobegin readln(x1,y1,x2,y2);new(p);p.h1:=y1;p.h2:=y2;p.next:=addx1;addx1:=p;new(p);p.h1:=

28、y1;p.h2:=y2;p.next:=delx2;delx2:=p;end;,new(tree);build(tree,0,30000);sum:=0;for i:=0 to 30000 dobegin p:=deli;while pnil do begin update(tree,p.h1,p.h2,0);p:=p.next;end;p:=addi;while pnil do begin update(tree,p.h1,p.h2,1);p:=p.next;end;if tree.delta0 then sum:=sum+30000 else sum:=sum+tree.sum;end;w

29、riteln(sum);,应用举例,例6、蛇在平面上有N个点，现在要用一些线段将它们连起来，使其满足以下要求：（1）这些线段必须闭合（2）线段的端点只能是这N个点（3）交于一点的两条线段成90度角（4）线段都必须平行于X轴或Y轴（5）所有线段除了在这N个点外不相交（6）所有线段的长度之和必须最短如果存在这样的线段，则输出最小长度，否则输出0。,应用举例（蛇）,1、所有线段都要和坐标轴平行，所以每个点只能与上下左右四个点相连，由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。2、在同一水平线上的点中，按X轴排序后设为P1，P2，Pn，P1必须与P2相连，

30、P3必须与P4相连，在同一垂直线上的点也同样，所以线段的构造是唯一的。,应用举例（蛇）,3、由于解是唯一的，是否相连只要广度扩展就可判断了，关键在于判断由上述方法所构造出的线段是否合法（满足线段不在N个点之外自交）。,不相连不合法,不自交合法,自交不合法,应用举例（蛇）,4、由于所有线段与坐标轴平行，有明显的区间性，可以用线段树判断是否自交：（1）先将所有的线段按X坐标排序，注意线段在端点重合不算自交，所以X轴坐标相同时，事件的顺序要恰当处理：右端点优先，其次是与Y轴平行的线段，最后是左端点。,应用举例（蛇）,（2）将Y轴表示的区间建立线段树，每个线段或线段的端点作为一个事件。按X坐标由小到大

31、，扫描所有事件：平行于X轴线段的左端点，就把Y坐标插入到线段树中；平行于X轴线段的右端点，就把Y坐标从线段树中删除；平行于Y轴的线段，假设该线段的Y坐标分别为y1和y2，就在线段树中查询y1，y2区间内是否有点存在，如果存在就说明有线段和它相交，该图形不合法。,线段树与RMQ的比较,RMQ提供了一种高效的计算区间最值的方法。它的思想是将询问区间分解成两个最大的2的次幂的长度的区间并的形式。与线段树不同，这种区间分解是存在相交的分解。因此RMQ只能维护一些简单的信息，比如最值。,线段树与RMQ的比较,RMQ的优势：（1）实现非常简单；（2）效率比线段树更高；线段树的优势：（1）可以更好地维护动态

32、的信息，而RMQ不推广到动态；（2）可以维护更多的信息，而RMQ只能维护最值。,线段树与树状数组的比较,树状数组可以对单个元素进行高效的修改，并且可以高效的求部分和。由于使用了位运算，因此树状数组的效率要优于线段树。树状数组的空间开销也比线段树要小，但是树状数组的应用范围没有线段树广，能够转化使用树状数组的情况下尽量使用树状数组。,线段树与平衡树的比较,这两种数据结构解决了不同方面的问题，但是有的题目通过适当的建模，使用两种数据结构都能够加以解决。通常情况下，使用线段树的效率会优于平衡树。但线段树有一点局限性：尽管能够在区间上进行修改操作，但不能插入或者删除区间。而这种插入与删除操作却是平衡树的基本操作之一。,参考资料,线段树：线段树及其应用NOI专刊2009年第1期 线段树及其应用2009年冬令营小营讲课 数据结构（七）NOI专刊2007年第7期 Picture题目解析NOI专刊2008年第2期RMQ：RMQ在信息学竞赛中的应用NOI专刊2008年第8期树状数组：树状数组简介NOI专刊2008年第9期平衡树：数据结构（六）NOI专刊2007年第6期,晚间讨论,线段树与数据结构（如RMQ、排序树、平衡树、树状数组、堆）的区别和适用题型。,