你的進度
0/ 33 節已標記完成
下一節: 二元索引樹:區間、更新與前綴和
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI2740 筆記裏的內容
數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 97 · 定義 54 · 反例 50 · 概念視角 17 · 證明透視 47
第 1 章 · 5 節
區間查詢
從儲存區間的不變量推導 Fenwick 樹的查詢與更新,證明對數時間界,並區分增量、賦值及最小值查詢。
- 1.1
二元索引樹:區間、更新與前綴和
從儲存區間的不變量推導 Fenwick 樹的查詢與更新,證明對數時間界,並區分增量、賦值及最小值查詢。
- 1.2
用線段樹處理賦值與區間最小值
證明線段樹的不變量,以及單點賦值下對數時間區間最小值查詢。
- 1.3
線段樹:結合式摘要與有序區間查詢
推導結合式摘要的有序線段查詢,並區分單點更新及延遲傳播。
- 1.4
二維前綴和與矩形差分
推導四角總和查詢與離線矩形加法,明確處理半開邊界、空矩形及預處理成本。
- 1.5
平方根分塊:延後加法與區間總和
分清儲存值、延後區塊加量與真實區塊總和,證明可交錯執行的區間加法及總和查詢。
第 2 章 · 1 節
2. 靜態區間查詢
預處理二的冪長度區間以查詢靜態最小值。
- 2.1
靜態區間最小值的稀疏表
證明二的冪長度區間不變量,解釋重疊最小值查詢。
第 3 章 · 1 節
圖的連通性
無向多重圖的 DFS low-link 與橋邊。
- 3.1
無向多重圖中的 DFS 橋邊
保留平行邊身分,證明 low-link 橋邊判準。
第 4 章 · 1 節
區間更新
以端點差分處理區間加法與單點值。
- 4.1
差分陣列與區間加法端點
證明離線區間加法的端點不變量,並連繫 Fenwick 單點查詢。
第 5 章 · 1 節
無偏遊戲
有限正常玩法、mex 與異或。
- 5.1
無偏遊戲的 mex 值與異或
證明有限無偏正常玩法遊戲的異或法則,並跟蹤取子遊戲。
第 6 章 · 1 節
因數篩法
Möbius 因數和及互質配對計數。
- 6.1
Möbius 因數和與互質配對
證明因數指示式,並以倍數篩計算互質索引對。
第 7 章 · 1 節
加權區間排程
由相容前綴建立動態規劃。
- 7.1
加權區間排程
推導加權區間的前驅遞推、重建及複雜度。
第 8 章 · 3 節
計算幾何
利用定向與有向面積判斷點相對於凸多邊形的位置。
- 8.1
有向面積與凸多邊形內的點
運用叉積、邊界測試與鞋帶和,明確說明凸性及整數範圍假設。
- 8.2
方向與閉線段相交
精確分類線段相交,包括共線和退化情形。
- 8.3
單調鏈凸包與共線點
構造凸包極點並證明按列分組的單調鏈算法。
第 9 章 · 2 節
字串算法
利用前後綴及回退搜尋重疊字串。
- 9.1
KMP 字串匹配:前後綴、回退與重疊匹配
從巢狀前後綴推導前綴函數,證明線性搜尋,保留重疊出現,並由最長真前後綴求最小週期。
- 9.2
Z 陣列、區間重用與精確字串匹配
證明前綴匹配重用的線性複雜度,並用 Z 值求精確匹配、前後綴與週期。
第 10 章 · 3 節
圖搜索與連通性
低鏈值、橋邊、有向分量與刪點。
- 10.1
迭代低鏈值搜索與橋森林
追蹤以邊編號實作的迭代低鏈值計算,並構造由橋連結的森林。
- 10.2
強連通分量、完成次序與凝聚圖
推導兩遍有向 DFS 算法及其無環凝聚圖。
- 10.3
割點、DFS 根與刪點後的連通分量數
推導 low-link 刪點判準並計算餘下連通分量。
第 11 章 · 1 節
二進冪
迴圈不變量、模冪及矩陣應用。
- 11.1
二進冪:迴圈不變量、矩陣遞推與遊走計數
不靠交換律證明二進冪並應用矩陣冪。
第 12 章 · 1 節
單調佇列
視窗極值、支配關係與攤銷成本。
- 12.1
滑動視窗最小值:支配、到期與單調雙端佇列
證明支配關係、處理重複值並界定雙端佇列總工作量。
第 13 章 · 2 節
輕重鏈剖分
樹路徑、子樹大小與區間查詢邊界。
- 13.1
輕重鏈路徑與查詢邊界
證明輕邊數量界,並把頂點及邊路徑劃分為區間查詢。
- 13.2
祖先倍增、第 k 祖先與最近共同祖先
組合父映射的冪,證明最近共同祖先的同步跳躍不變量,並在靜態樹查詢中避免虛構根以上的祖先。
第 14 章 · 2 節
子集動態規劃
精確已訪集合狀態、路線代價與最優路線。
- 14.1
子集狀態、哈密頓巡迴與最優路線
推導精確已訪集合動態規劃並還原最優有向巡迴。
- 14.2
遞增子序列:最小尾值與有效見證
證明最小尾值不變量,處理相等值,並重建真正的子序列而不是把尾值陣列當作見證。
第 17 章 · 2 節
數論
同餘式、中國剩餘定理與線性篩法。
- 17.1
精確算法:同餘與幾何定向
以擴展歐幾里得算法解線性同餘式,在模數不必互質時合併同餘式,並為定向測試與模冪保持精確的邊界檢查。
- 17.2
線性篩法:最小質因數與多次分解查詢
證明合成數的唯一生成規則,建立最小質因數表,並說清楚質因數提取的預處理、輸出及算術成本。
第 16 章 · 3 節
最短路徑
含負圈的 Bellman-Ford,以及使用雙端佇列的 0-1 BFS。
- 16.1
同步 Bellman–Ford:最短途徑、負圈,以及額外一輪所證明的事
證明 Bellman-Ford 背後的限長遞推式,把距離分為有限、無窮及負無窮,並說明額外一輪所能證明的事。
- 16.2
0–1 BFS:為甚麼雙端佇列可以取代優先佇列
當每條邊的成本為 0 或 1 時,用雙端佇列計算最短距離,並證明雙鍵不變量、處理過時項目及分析複雜度。
- 16.3
Dijkstra 與 Floyd–Warshall:單源與全點對最短路徑
證明非負權重下的 Dijkstra 算法,指出負權邊究竟在哪一步令它失效,並推導計算全點對距離的 Floyd–Warshall 遞推式。
第 15 章 · 1 節
搜尋與答案二分
對單調可行性判斷進行二分搜尋。
- 15.1
對容量進行二分搜尋:先證明可行性測試
把最小化問題化為單調的是非判斷,證明貪心可行性測試,並以安全的上下界與運算對答案進行二分搜尋。
第 18 章 · 1 節
最小生成樹
不相交集合、Kruskal 與 Prim,以及割性質。
- 18.1
不相交集合、Kruskal 算法與 Prim 算法
證明最小生成樹的割性質,在不相交集合並查集上實作 Kruskal 算法,並與 Prim 算法比較。
第 19 章 · 1 節
貪心算法
區間調度與工作次序的交換論證。
- 19.1
貪心算法與交換論證:區間調度與最優工作次序
闡明貪心選擇的證明模式,並以交換論證證明區間調度及按加權完成時間排序的貪心規則,同時說明為何看似合理的貪心規則會失敗。