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

题目： 假设希望对一组区间记录一个最大重叠点，亦即覆盖它的区间最多的那个点。 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：对信息的维护  步骤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)