算法合集之線段跳表——跳表的一個拓展(編輯修改稿)
2025-11-14 18:37 本頁面
【文章內容簡介】 樹 跳表中的隱式線段樹 進一步，將每個節(jié)點 v的查找路徑上節(jié)點都標記上 v。即可得到： 跳表中的隱式線段樹 再進一步，將標記值換成一個左閉右開的區(qū)間。再在第一層之下加入第零層。向第一層節(jié)點添加下行指針。 跳表中的隱式線段樹 我將這樣包含區(qū)間信息的跳表稱為線段跳表 區(qū)間的左邊界為該節(jié)點的索引值。 而區(qū)間的右邊界可以敘述如下： 設搜索該節(jié)點過程中最后一次經歷的縱向邊為 uv，則該節(jié)點右邊界為 u的后繼節(jié)點的索引值。該值不需額外存儲，每次搜索過程中即可動態(tài)獲得。 兩類區(qū)間信息的維護 DP 信息 (DPi)： 樹形 DP時存儲的某一區(qū)間的信息。. 區(qū)間內的點的個數
教學課件相關推薦
鄂ICP備17016276號-1