題目:
假設希望對一組區間記錄一個最大重疊點,亦即覆蓋它的區間最多的那個點。
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)
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支