算法导论-14-1-最大重叠点

最后更新于:2022-04-01 07:35:42

题目: 假设希望对一组区间记录一个最大重叠点,亦即覆盖它的区间最多的那个点。 a)证明:最大重叠点总存在于某段的端点上。 b)设计一数据结构,能有效地支持操作INTERVAL-INSERT,INTERVAL-DELETE和返回最大重叠点操作FIND-POM。(提示:将所有端点组织成红黑树。左端点关联+1值,而右端点关联-1值。附加一些维护最大重叠点的信息以扩张树中结点。) 思考: 设有n个区间,将所有2n个点从小到大排序,对于排序后的第i个点,若它是某个区间的左端点,则p[i]=1,若它是某个区间的右端点,则p[i]=-1。由第一问可知,所求的点一定是某条线段的端点,所以从端点集合中找出被最多区间覆盖的那个。若一个端点是排序后的第i个点,则有个SUM(s[1],s[i])个区间覆盖这个点。 使用红黑树对所有的端点进行动态排序并保证有较好的性质,在树的结点中增加一些顺序统计量的信息,用于求SUM(s[1],s[i]) 步骤1:基础数据结构 红黑树,p[x]=1表示它是区间的左端点,p[x]=-1表示它是区间的右端点 步骤2:附加信息 v[x]:以x为根的所有结点的p值之和 m[x]:MAX(SUM([left[x], i)) o[x]:以x为根的所有结点中的最大覆盖点 步骤3:对信息的维护 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-02_56b02bd3f34d9.gif) 步骤4:设计新的操作 Find_Pom():返回根结点的p值 代码: [头文件](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter14/section14_1.h) [产品代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/section14_1.cpp) [测试代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter14/section14_1Test.cpp)
';