→ FRAXIS: 可不可以簡單介紹一下莫隊算法的功用啊？ 02/05 01:26
現在有許多個區間查詢 Q = { [a1,b1] , [a2,b2] , ... , [ak,bk] }
預計其查詢結果是 r[a1,b1] ... r[ak,bk]
假設問題具備此性質：
已知 r[a,b] ，可以快速求得邊界差一的結果如 r[a-1,b] r[a+1,b] r[a,b-1] r[a,b+1]
令計算時間為 O(f(n))
那麼，已知 r[ai,bi] 推得 r[aj,bj] 的時間就是 O((|ai-aj| + |bi-bj|) * f(n))
即 rectangular distance (L1)
我們現在替 Q 中所有查詢，安排適當計算順序，讓總時間最少。
查詢視為座標，即 minimum spanning tree with rectangular distance O(k log k)
找到樹之後，跑個DFS或BFS，就得到最佳的計算順序。
(理論上 steiner tree 效果更好，不過它是 NP-hard ...)
我理解的莫隊算法是這樣。
至於為什麼莫隊算法宣稱 O(n^1.5) ，我還沒搞清楚...