pkuacm_summar3(1)(数据结构选讲).ppt

《pkuacm_summar3(1)(数据结构选讲).ppt》由会员分享，可在线阅读，更多相关《pkuacm_summar3(1)(数据结构选讲).ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、pkuacm_summar3(1)(数据结构选讲) Four short words sum up what has lifted most successful Four short words sum up what has lifted most successful individuals above the crowd: a little bit more. individuals above the crowd: a little bit more. -author -author -date-date线段树(树状数组)伸展树自动机后缀数组并查集function 以节点v为根建树、

2、区间为l,r 对节点v初始化 if (l!=r) 以v的左孩子为根建树、区间为l,(l+r)/2 以v的右孩子为根建树、区间为(l+r)/2+1,r 2、线段树把区间上的任意一条线段都分成不超过2logL条线段。这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据 n1、线段树的深度不超过logL。给定data0datan-1每个指令为下面两种操作中的一种： 给定k，修改datak的值 询问一个区间l,r里的dataldatar的最小值把data5的值修改为10function 修改以节点v为根的子树、区间为l,r 如果修改点不属于l,r 跳出 修改节

3、点v的值 if (l!=r) 以v的左孩子为根建树、区间为l,(l+r)/2 以v的右孩子为根建树、区间为(l+r)/2+1,r 查询data1data7中的最小值function 在节点v查询区间x,y if v所表示的区间与x,y的交集为空， 跳出 if v所表示的区间完全属于x,y 选取v else 在v的左孩子查询x,y 在v的右孩子查询x,y 有一个轨道，开始高度都为0给定一系列指令，每个指令为下面两种操作中的一种： 改变a,b的斜率为d 求最大的k，使得0,k中任意高度不超过h指令数100000轨道长度1000000000斜率height=p的左孩子-height+p的右孩子-he

4、ight p-max=maxp的左孩子-max, p的左孩子-height+p的右孩子-max如何处理巨大的轨道长度？方法1、离散化 优点：方法常见，实现简单 缺点：需预先知道所有的长度，是离线算法方法2、动态申请空间假设长度为10开始只有一个根节点0,9插入1,7后方法2、动态申请空间 优点：可以处理无法预先知道所有长度的题目，是在线算法 缺点：时间与空间复杂度都是O(nlogc) 而方法一的时间复杂度是O(nlogn) 空间复杂度为O(n)给定n1条平行于x轴的直线，n2条平行于y轴的直线，n3个点(n1,n2,n31001) 且坐标范围1001统计包含点的正方形个数，要求正方形的四条边都

5、在给定的直线上题目设置了两个障碍： 目标是统计正方形的个数，不是长方形的个数 要求正方形中有点很自然的想法：枚举边长首先枚举边长k如果知道了正方形的左边界L，也就可以知道正方形的右边界L+k，那么x坐标在L,L+k中的点在正方形中的x坐标就不影响了，二维问题转化成了一维问题现在的问题是：已知一条线段上所有点的位置，如何快速满足下列条件的线段的个数： 长度为k 包含点 线段端点选自于给定的表中要考虑长度为k的线段条数并不容易变通：线段中包含点，也可以转化为把点延长到长度为k，要求线段的一个端点在这个区间内问题转化为： 每个点有一个权值（由最初给定的直线决定） 插入（删除）一些线段，线段覆盖了一些

6、点 求被覆盖的点的权值和原数组是a，c是a的树状数组可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5C8=a1+a2+a3+a4+a5+a6+a7+a8C2n=a1+a2+.+a2n对于序列a，我们设一个数组C Ci = ai 2k + 1 + + ai k为i在二进制下末尾0的个数C即为a的树状数组如何求k？2k=x &(x(x-1) 以6为例 (6)10=(0110)2xor 6-1=(5)10=(0101)2 (0011)2and (6)10=(0110)2 (0010)2void change(int k,int delta); while (

7、k0) t+=ck,k-=lowbit(k);return t;树状数组VS线段树优点：代码简单、空间时间常数小缺点：有哪些题线段树可以做，树状数组不能做的？ 树状数组能解决的问题大多为求和问题，如果已知节点p的值和p的左孩子的值，能推出p的右孩子的值，大多可以用树状数组解决伸展树(Splay Tree)是二叉查找树的改进，比一般二叉查找树再加了伸展操作伸展操作的目的是使二叉查找树尽可能随机，避免退化对伸展树的操作的平摊复杂度是O(log2n)。伸展树的空间要求、编程难度相对于其它平衡二叉树来说非常低。伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树S中的元

8、素x调整至树的根部的操作。在旋转的过程中，要分三种情况分别处理： 1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig Zig或Zag操作： 节点x的父节点y是根节点。Zig-Zig或Zag-Zag操作： 节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。 Zig-Zag或Zag-Zig操作： 节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。 Join(S1,S2)：将两个伸展树S1与S2合并。其中S1的所有元素都小于S2的所有元素。首先，找到伸展树S1中的最大元素x

9、，再通过Splay(x,S1)将x调整为S1的根。然后将S2作为x节点的右子树。这样，就得到了新伸展树S。Split(x,S)：以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。 首先执行Find(x,S)，将元素x调整为伸展树的根节点，则x的左子树就是S1，而右子树为S2。伸展树不仅可以处理点的问题，也可以处理线段的问题处理点的问题，往往可以用stl里的set、map解决处理线段的问题：在每个点记录以这个点为根的子树的整体信息(如求最小值时，就是记这个子树中所有点的最小值)插入、删除、查找、求值等操作的维护，都与线段树相近但更加灵活，因为树

10、的结构也是可变的可以说，伸展操作是伸展树的精髓给定N个数P1 P2 PN (Nmin=p的左孩子min) p=p的左孩子 else if (p-min=p的右孩子min) p=p的右孩子 else 返回p； 返回p;翻转x,y用分离操作把1,n分离成：1,x-1,x,y, y+1,n改变x,y这段根的标记用合并操作把三段合并起来伸展树VS线段树缺点：代码麻烦，时间空间常数大优点：能处理线段树不能处理的问题（如翻转等）很容易有这样的问题，在二维中，线段树还可用吗？2、线段树把区间上的任意一条线段都分成不超过2logL条线段。这些结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找

11、等工作，提供了理论依据而这种树结构不能保证第2条，所以会退化n1、线段树的深度不超过logL。需要采用树套树，即每个线段树的节点l,r也保存一个线段树，保存横坐标在l,r间的集体情况所有性质与线段树类似，插入、删除、查找等时间复杂度为O(log2n)。问题描述：在一个长为D、宽为S、无限高的3维空间里，开始丢N个俄罗斯方块(长方体)。长方体会一直下落到碰到了已有长方体为止。给定每个长方体的长、宽、高以及长方体的位置坐标，问所有长方体下落完之后，整个空间里最高点的高度。（N=20000 D，Smax 否则若当前区间与询问区间相交， 则返回maxp-cover,ask(p-left),ask(p-

12、right)处理插入操作function insert(p,k) 若当前区间被插入区间整段覆盖，p-cover?=k;p-max?=k 否则若当前区间与插入区间相交， p-max?=k 插入进当前区间的的左孩子和右孩子缺点： 没有利用到行与行之间的连续性，时间复杂度O(NSlogD)。会超时因此，考虑二维线段树：一维中，我们对于每个区间记录2个信息，那么扩展到二维，就要记录4个信息： 行被整段覆盖，列也被整段覆盖的最大高度cover,cover 行中的某点，列被整段覆盖的最大高度max,cover 行被整段覆盖，列中的某点最大高度cover,max 区域里的某点的最大高度max,max在处理询

13、问和插入操作时，需要先递归的分行，再分列，对与行列分别操作，且操作方法和一维是基本上相同的时间复杂度为O(NLogslogd)。空间复杂度为(SD)。处理询问操作function asky(sign=(max/cover),p) 若当前区间被询问区间整段覆盖，返回p-sign,max 否则若当前区间与询问区间相交， 则返回maxp-sign,cover,ask(sign,p-left),ask(sign,p-right)function askx(p) 若当前区间被询问区间整段覆盖，asky(max) 否则若当前区间与询问区间相交， 则返回maxasky(cover),ask(p-left),

14、ask(p-right)处理插入操作function inserty(sign=(cover/max),p,k)若当前区间被插入区间整段覆盖，p-sign,cover?=k;p-sign,max?=k 否则若当前区间与插入区间相交， p-sign,max?=k 插入进当前区间的的左孩子和右孩子function insertx(p,k)若当前区间被插入区间整段覆盖，inserty(cover,p,k) inserty(max,p,k) 否则若当前区间与插入区间相交， inserty(max,p,k) 插入进当前区间的的左孩子和右孩子在nn矩形里，有两种操作1、同时给一个矩形内所有数增加一个相同值

15、2、询问一个矩形内所有数之和三维线段树、四维线段树。有一些竹子，给定它们的位置，数量L以及可口度D熊猫每次吃竹子都要比以前吃的更可口，并且与上次吃竹子的位置的曼哈顿距离不能超过这次竹子的数量问熊猫最多能吃到多少次竹子由于要求以竹子的可口度为序，很容易联想到动态规划。先按照可口度排序，然后用f(i)表示熊猫最后一次吃了第i个竹子的情况下，最多吃了多少次竹子。则f(i)=maxf(j)+1 (ji且|xi-xj|+|yi-yj|=Li)。这样做是O(n2)的。显然会超时。仔细观察这个方程，发现：|xi-xj|+|yi-yj|=Li这个区域实际上是个正方形如果我们能利用二维线段树，把每个点的f值插入

16、到它的坐标上，然后每次只要查询|xi-xj|+|yi-yj|=Li这个正方形里的最大值，就可以在O(log2n)的时间内算出每个f了。不过这个正方形是立着的，为了方便计算，我们首先把所有坐标都旋转45度，这样这些正方形就变成了我们经常处理到的躺着的正方体。假设某个点的坐标为(x,y)，则旋转后它的坐标为（x+y,y-x），|xi-xj|+|yi-yj|=Li这块区域的坐标就是以(xj+yj-Li,yj-li-xj)为左上角以(xj+yj+li,yj+li-xj)为右下角的矩形区域。这样这个问题就成为了标准线段树问题。如何处理巨大的坐标范围？方法1、离散化 可把坐标范围106降低到105，但是由

17、于是二维的，所以空间需要1010，依然行不通方法2、动态申请空间由于线段树的深度为O(log2N)，而每进入一层线段树都会多需要一个节点，而且这些节点有可能被公用，也可能单独使用，所以最坏的情况下，会出来O(Nlog2N)个节点空间复杂度为O(Nlog2N)，遗憾的是，对于N=100000的情况，还是大了点之所以会太大，是因为二维线段树的2维分别把一个节点变成了logN个。如何改变这种浪费呢？处理这个问题，还可以考虑平衡树。使用平衡树并不会产生多余的节点，每个点放入平衡树中，还有只有1个点。如果能把第二维的线段树改为平衡树，空间复杂度可以降低到O(NlogN)，这样就可以承受了。平衡树的一维处

18、理需要记录这样的内容： 当前点的f， 以当前点位根的子树中f的最大值 它的纵坐标 左孩子和右孩子。平衡树以它的纵坐标为序。至于如何插入和查询，应该是大家很熟悉的了，这里就不再赘述了。线段树套平衡树时，只需要把一个点插入到线段树上路径上每个点的平衡树里。这个问题看似容易，但由于坐标范围巨大，导致了时间足够但空间不够。从这里我们发现，单单掌握线段树是不够的，还需要合理运用各种数据结构，并分析出它们各自的优势和缺陷，才能做好数据结构问题。线段树、树状数组、伸展树都是acm程序设计竞赛中的基本数据结构，它们的基本操作希望大家能熟练掌握数据结构题的难点往往不在于实现，而在于对问题的具体分析，最重要的是要掌握各种数据结构能解决什么样的题，这样为进一步分析提供了方向当然，题目千变万化，还需具体问题具体分析，不断产生新的思路，这也是竞赛中最有趣的地方