线段树111ppt课件

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=k=n，d为整数) SUM s t （表示输出As+At） 输出：对于每一个SUM提问，输出结果,如果按题目要求直接模拟： 每一个ADD操作的复杂度是O(1) 每一个SUM操作的复杂度是O(N) 可见对于M次SUM询问，复杂度是O(NM) 有没有更好的方法呢？这里我们提出一种称之为线段树的数据结构。,引例 数列操作,线段树,在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。,表示区间1, 10的线段树样例：,树：是一棵树，而且是一棵二叉树。 线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数) 同一层的节点所代表的区间，相互不会重叠。 叶子节点的区间是单位长度，不能再分了,线段树的定义,线段树是一棵二叉树，记为T(a, b)，参数a,b表示区间a,b，其中b-a称为区间的长度，记为L。 线段树T(a,b)也可递归定义为： 若L1 : a, (a+b) / 2为 T的左儿子； (a+b)/ 2,b为T 的右儿子。 若L=1 : T为叶子节点。,线段树的特征,线段树把区间上的任意一条线段都分成不超过2logL条线段,定理：线段树的深度不超过logL。,这个结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据,线段树的运用,线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。,区间统计,举一个例子： 给n个数K1, K2 . Kn 有m个询问，每次询问你从第i个数到第j个数的和。,显然，这是一个区间统计问题，让你统计i, j区间上的元素和。 最简单的思想是对于每个询问，我用循环加一遍，即可得到答案。 这个算法的正确性不容质疑，可时间复杂度呢？ 每次询问最多可能从K1加到Kn，用循环的话要加n次，所以每次询问的复杂度是O( n )，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次修改复杂度是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 思考：进到子结点的判断条件是什么？提示：注意观察线段树的组成,线段树,上面的询问中，需要每个结点T的都要保存自己表示区间的元素的和。如果其中有某个元素被修改，则T所表示的和也要修改，称之为维护。 对于每次修改，必须对线段树一些结点进行维护，才能保证询问时得到正确解。 下面给出的伪代码会在O(lgN)的复杂度实现维护。,线段树,维护伪代码，将Ki修改为X，相当于将i,i修改为X void Modify( T ) if ( T左边界 = T右边界 ) T中元素和 = X /因为T中仅有一个元素 else mid = ( T左边界 + T右边界 ) / 2 value = 0 if ( i mid ) value += Modify( T右子结点 ) 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 ) / 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,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？,分析,这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：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），此方法效率太低。,离散化的做法,基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其应用前一种算法，再将最后结果转化回来得解。 该方法对于线段数相对较少的情况有效。,示例,10000,22000 30300,55000 44000,60000 55000,60000 排序得10000，22000，30300，44000，55000，60000 对应得1 ，2 ，3 ，4 ，5 ，6 1,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 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,线段树的数据结构表示,1、动态数据结构 2、完全二叉树,动态数据结构,Typedef struct pnode int 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 TreeNode int b, e; int cover; tree4*M;,对应区间,插入算法,Void Insert(int p,int a,int b) int m; if (Treep.cover = 0) m = (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; ,被完全覆盖,是单位区间,二分递归求解,事实上，我们也可以不在每个节点中保存其表示范围，而是在递归调用时增加两个参数来加以表示。,完全二叉树de另一种定义,Typedef struct TreeNode int 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= 0 else Count = Count2(p * 2, l, (l + r) 2) + Count2(p * 2 + 1, (l + r) 2, r); return count; ,这个也一样,例2,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。,Wall,分析,可以这样来看这道题：x轴上有若干条不同线段，将它们依次染上不同的颜色，问最后能看到多少种不同的颜色？（后染的颜色会覆盖原先的颜色） 我们可以这样规定：x轴初始是颜色0，第一条线段染颜色1，第二条线段染颜色2，以此类推。,分析,原先构造线段树的方法不再适用，但是我们可以通过修改线段树的cover域的定义，使得这道题也能用线段树来解。 定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。,插入算法,Void Insert(int p,int l, int r, int a,int b,int c) int m; if (Treep.cover != c) m= (l + r) 2; if (a = l) ,未被完全覆盖或者染色不同,为什么？ 有可能越界吗？,插入算法,Treep * 2 + 1.cover = Treep.cover; Treep.cover = -1; if (b=m) Insert(p * 2 + 1, m, r, a, b, c); else Insert(p * 2, l, m, a, m, c); Insert(p * 2 + 1, m, r, m, b, c); ,未被完全覆盖或者染色不同,为什么？ 有可能越界吗？,统计算法,使用一个数组Flag，初始化为0。遍历线段树，对于每种颜色c对Flagc赋值1。最后统计Flag中1的个数即可。（注意颜色0应该排除在外，可以在最后减1）,统计算法,void Count(int p, int l, int r) if (Treep.cover = 0) FlagTreep.cover= 1; else if (r l) 1) Count(p * 2, l, (l + r) 2); Count(p * 2 + 1, (l + r) 2, r); ,例3,把例2稍加改动，规定：线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成多少段。,分析,仍然定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。,插入算法,插入算法不变,统计算法,Int Count(int p,int l,int r,int lc,int rc) int result, tl, tr; if (Treep.cover = 0) lc = Treep.cover; rc = Treep.cover; if (Treep.cover 0) result = 1; else result = 0; ,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身 非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,统计算法,else if (r l 1) result =Count(p * 2, l, (l + r) 2, lc, tl) + Count(p * 2 + 1, (l + r) 2, r, tr, rc); if (tl = tr) ,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身 非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,例4,x轴上有若干条不同线段，问某个单位区间x,x+1上重叠了多少条线段？,分析,为线段树每个节点增加一个Count域。表示所对应区间上重叠的线段数。 思考线段树的构造方法：当某线段能够完整覆盖某个结点所对应的区间时，则不再二分。因此要统计某个单位区间上重叠的线段总数，必须把从叶结点到根结点路径上所有结点的count域累加。,插入算法,void Insert(int p, l, r, a, b) int m; m = (l + r) 2; if (a = l) ,统计算法,Int Cou(int p) int result; result= 0; while p 0) result= result + Treep.count; p= p / 2; return result; ,POJ2182,大致题意：有一个N个数组成的数列，是1到N的某个排列，知道第i数前面比他大的数有Ki个，求出这个数列。 思路：对于最后一个数Fn，其前面有Kn个比他大的数，由于数列是1到N的全排列，所以Fn就是N-Kn。再来看Fn-1，其前面有Kn-1个比他大的数，那么Fn-1应该就是除了Fn之外的所有数中第Kn-1 + 1 大的数。,继续推下去，可以得出：Fi就是除了Fi+1,Fi+2Fn之外的数中第Ki + 1大的数。 非常好，我们就利用这个性质来逆向推出这个数列所有的值。,嘿嘿，这时寻求分析自然而然的就来了。 我们需要一个数据结构，他能求出第K大的数，并且支持删除操作。 什么数据结构可以满足？ 1.BST（回忆上一讲的一个问题） 2.线段树,权衡 用STL的set是无法在O( lgN )实现这样的BST的。所以要手写BST上帝啊囧 相比之下，自己设计的线段树实现比较容易，且效率不低，可以采纳！,继续分析：如何用线段树实现？ 我要求的是第K大的数，如果每个结点都保存自己表示区间中覆盖的元素个数，那么嘿嘿，你想到了？ 厉害！ 保存的这个值可维护么？显然可以在O( lgN )维护，good，线段树设计完毕了。,例5,一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间a,b中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,用线段树解,为线段树每个节点增加一个Count域。表示所对应区间内元素之和。 每次修改一个格子，需要修改从叶结点到根结点路径上所有结点的值。 特别注意：题目中的区间是以元素为端点，因此a,b和b,c存在重合，这和我们之前讨论的区间定义不同。我们这里忽略预处理过程，直接使用之前的区间定义。,a b c,定义,type TreeNode = record count: Integer; end;,插入算法,procedure Modify(p, delta: Integer); begin repeat Treep.count := Treep.count + delta; p := p div 2; until p = 0; end;,统计算法,function Count(p, l, r, a, b: Integer): Integer; var m: Integer; begin if (l = a) and (r = b) then Count := Treep.count else begin m := (l + r) div 2; if b = m then Count := Count(p * 2 + 1, m, r, a, b) else Count := Count(p * 2, l, m, a, m) + Count(p * 2 + 1, m, r, m, b); end; end;,介绍另一种算法,对于序列a，我们设一个数组C，定义 Ci = ai 2k + 1 + + ai，k为i在二进制下末尾0的个数。,图例,(1)10=(0001)2,(2)10=(0010)2,(3)10=(0011)2,(4)10=(0100)2,(5)10=(0101)2,(6)10=(0110)2,(7)10=(0111)2,(9)10=(1001)2,(8)10=(1000)2,如何计算x对应的2k？,2k=x and (x xor (x-1) 以6为例 (6)10=(0110)2 xor 6-1=(5)10=(0101)2 (0011)2 and (6)10=(0110)2 (0010)2,k为x在二进制数下末尾0的个数。,function Lowbit(x: Integer): Integer; begin Lowbit := x and (x xor (x 1); end;,如何计算某个区间a,b的和sum(a, b),我们这里所说的区间以元素为端点 把这个问题转化成为求sum(1,b)-sum(1,a-1) 如何求sum(1,x)？,求和算法,function Sum(x: Integer): Integer; var result: Integer; begin result := 0; while x 0 do begin result := result + Cx; x := x Lowbit(x); end; Sum := result; end;,如何修改一个元素的值,设要修改的元素是ap 任意x满足x=pxLow