《线段树111ppt课件》由会员分享，可在线阅读，更多相关《线段树111ppt课件（88页珍藏版）》请在金锄头文库上搜索。
1、ACM集训之 线段树,引例 数列操作,假设有一列数Ai(1in)，支持如下两种操作： 将Ak的值加D。（k, D是输入的数） 输出As+As+1+At。（s, t都是输入的数，ST）输入：第一行一个整数n，第二行为n个整数，表示Ai的初始值。第三行为一个整数m，表示操作数下接m行，每行描述一个操作，有如下两种情况：ADD k d (表示将Ak加d，1=k1 : a, (a+b) / 2为 T的左儿子；(a+b)/ 2,b为T 的右儿子。 若L=1 : T为叶子节点。,线段树的特征,线段树把区间上的任意一条线段都分成不超过2logL条线段,定理：线段树的深度不超过logL。,这个结论为线段树能在
2、O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据,线段树的运用,线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。,区间统计,举一个例子： 给n个数K1, K2 . Kn 有m个询问，每次询问你从第i个数到第j个数的和。,显然，这是一个区间统计问题，让你统计i, j区间上的元素和。 最简单的思想是对于每个询问，我用循环加一遍，即可得到答案。 这个算法的正确性不容质疑，可时间复杂度呢？ 每次询问最多可能从K1加到Kn，用循环的话要加n次，所以每次询问的复杂度是O( n )
3、，m次就是O( mn ),区间统计,分析：这n个数是不变的，我们可以在读入所有的数后预处理一下。 令 S0 = 0 Si = K1 + K2 + . Ki那么就有 sumi.j = Sj - Si-1,经过这样的预处理后，每次询问就可以在O(1)的时间复杂度内得到解决，m次就是O(m)了。思考：预处理的复杂度是多少？ 你能想到O(n)的预处理方法么？ 提示：利用 Si = Si-1 + Ki,区间统计,现在增加一些难度： 在m个询问中穿插t个修改，每个修改要求将某个Ki修改成指定值如果还是用预处理S的方法，那么每次修改时维护S数组的代价是多少？O(n)的（你能说出理由吗？）这样t次修改复杂度是
4、O( tn )的，有没有更好的方法解决这个问题？,线段树,好，此时拿出我们的杀手锏线段树。,对于一个区间i,j都可以用线段树上最多2lgN个结点来表示。,线段树-变形，对点统计,线段树,假设现在用t个结点来表示一个区间A。 这t个结点表示的是A的t个子区间。如果我们知道这t个子区间中，每个子区间中Ki的和，加到一起就是A中所有Ki的和。找到这t个结点的复杂度O(lgN)，所以用线段树解决每次询问的复杂是O(lgN),线段树,现在给出如何找到这t个区间的伪代码/找begin, end中元素和 int Query( T ) if ( T左边界 = begin 思考：进到子结点的判断条件是什么？提示
5、：注意观察线段树的组成,线段树,上面的询问中，需要每个结点T的都要保存自己表示区间的元素的和。如果其中有某个元素被修改，则T所表示的和也要修改，称之为维护。对于每次修改，必须对线段树一些结点进行维护，才能保证询问时得到正确解。下面给出的伪代码会在O(lgN)的复杂度实现维护。,线段树,维护伪代码，将Ki修改为X，相当于将i,i修改为Xvoid Modify( T ) if ( T左边界 = T右边界 ) T中元素和 = X /因为T中仅有一个元素 else mid = ( T左边界 + T右边界 ) / 2 value = 0 if ( i mid ) value += Modify( T右子
6、结点 ) T中元素和 = value ,这样，修改和询问都可以在O(lgN)时间内解决。最后问题：如何表示线段树，如何建立线段树，如何初始化线段树。表示： struct node int sum, lbound, rbound; node *lchild, *rchild; ; node poolN*3, *alloc = pool, *root;,线段树,建树并初始化O( N )root = Create( 1, N );node * Create( int L, int R ) T = alloc+; T-lbound = L; T-rbound = R; mid = ( L + R )
7、/ 2; if ( L = R ) T-sum = KL; else T-lchild = Create( L, mid ); T-rchild = Create( mid+1,R ); T-sum = T-lchild-sum + T-rchild-sum; ,线段树,到此为止呢，前面提出的问题可以在 O( n + mlgn + tlgn )时间内解决。,例1,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？,分析,这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题
8、目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。,最直接的做法,设线段坐标范围为min,max。使用一个下标范围为min,max-1的一维数组，其中数组的第i个元素表示i,i+1的区间。数组元素初始化全部为0。对于每一条区间为a,b的线段，将a,b内所有对应的数组元素均设为1。最后统计数组中1的个数即可。,示例,初始情况 1，2 3，5 4，6 5，6,4个1,缺点,此方法的时间复杂度决定于下标范围的平方。 当下标范围很大时（0,10000），此方法效率太低。,离散化的做法,基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其应
9、用前一种算法，再将最后结果转化回来得解。 该方法对于线段数相对较少的情况有效。,示例,10000,22000 30300,55000 44000,60000 55000,60000 排序得10000，22000，30300，44000，55000，60000 对应得1 ，2 ，3 ，4 ，5 ，61,2 3,5 4,6 5,6,示例,初始情况 1，2 3，5 4，6 5，6,4个1,示例,10000，22000，30300，44000，55000，60000 1 ，2 ，3 ，4 ，5 ，6(22000-10000)+(60000-30300)=41700,1 2 3 4 5 6,10000
10、22000 30300 44000 55000 60000,缺点,此方法的时间复杂度决定于线段数的平方。 对于线段数较多的情况此方法效率太低。,使用线段树的做法,给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。,1,6,0,3,6,0,1,6,0,1,3,0,3,6,0,1,2,0,2,3,0,3,4,0,4,6,0,4,5,0,5,6,0,1,3,0,1,2,1,加入1,2,加入3,5,3,4,1,4,6,0,4,5,1,1,2,1,3,4,1,4,5,1,加入4,6,4,6,1,4,6,1,线段树的数据
11、结构表示,1、动态数据结构 2、完全二叉树,动态数据结构,Typedef struct pnodeint b,e;struct pnode *l,*r; int cover; *pt;,对应区间,左右孩子,5,9,完全二叉树,1,9,1,5,1,3,3,5,5,7,7,9,7,8,8,9,5,6,6,7,3,4,4,5,1,2,2,3,完全二叉树,Typedef struct TreeNodeint b, e; int cover; tree4*M;,对应区间,插入算法,Void Insert(int p,int a,int b) int m;if (Treep.cover = 0)m = (
12、Treep.b + Treep.e) 2;if (a = Treep.b) ,取中值,未被完全覆盖,完全覆盖,在左边,在右边,二分,统计算法,Int Count1(int p) int count;if (Treep.cover = 1)Count = Treep.e Treep.b;else if (Treep.e Treep.b = 1) Count= 0;else Count = Count(p * 2) + Count(p * 2 + 1); Return count; ,被完全覆盖,是单位区间,二分递归求解,事实上，我们也可以不在每个节点中保存其表示范围，而是在递归调用时增加两个参数
13、来加以表示。,完全二叉树de另一种定义,Typedef struct TreeNodeint cover; tree4*M;,对应区间,插入算法,void Insert(int p, l, r, a, b) int m;if (Treep.cover = 0)m= (l + r) 2;if (a = l) ,Treep.b换成了l，Treep.e换成了r，递归时需要多加两个参数，其余都一样,统计算法,Int Count2(int p, l, r) int count;if (Treep.cover = 1)Count = r - l;else if (r l = 1) Count= 0else Count = Count2(p * 2, l, (l + r) 2)+ Count2(p * 2 + 1, (l + r) 2, r);return count; ,
