作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 主席樹？
時間Thu Feb 5 13:46:44 2015
1F：→ 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) ，我還沒搞清楚...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.78.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1423115208.A.6A7.html
※ 編輯: DJWS (111.250.78.113), 02/05/2015 13:56:52
※ 編輯: DJWS (111.250.78.113), 02/05/2015 13:57:31
2F：推 dreamoon: 總覺得這種食後要貼出那個Let me google that for you.. 02/05 16:13
3F：推 FRAXIS: 挺有趣的技巧 我研究看看 02/05 23:17
4F：推 FRAXIS: 我有點搞不懂 那是不是把所有ai, bi 排序 一個一個作就好? 02/05 23:20
6F：→ DJWS: 按照XY座標排序之後順序 總距離通常較長 02/06 19:32
7F：→ DJWS: 然後圖中的直線改成階梯狀就是 rectangular distance 02/06 19:33
8F：推 FRAXIS: 了解了 感謝 02/06 22:17
9F：推 FRAXIS: 但是不能把整個空間分塊嗎？ 然後每一區塊選一個中心 02/06 22:38
10F：→ FRAXIS: 這樣就可以先preprocess 來 speed-up查詢 02/06 22:38
11F：推 FRAXIS: 我上網看了一下 大概了解是在幹嘛了.. 02/07 04:20
13F：→ DJWS: 這個算法跟區間查詢其實沒有直接關係 02/07 12:16
14F：→ DJWS: 這個技巧其實還可以套用到 dynamic programming 狀態轉移 02/07 12:17
15F：→ DJWS: 然後你講的也是一個好方法 應該就是ALT Algorithm 02/07 12:20
17F：→ FRAXIS: 這技巧應該是因為實作比較容易 02/07 23:11