Re: [問題] 主席樹？
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/02/05 13:46)推噓7(7推 0噓 9→)留言16則, 3人參與討論串2/4 (看更多)
→
02/05 01:26,
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://www.ptt.cc/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
推
02/05 16:13, , 1F
02/05 16:13, 1F
推
02/05 23:17, , 2F
02/05 23:17, 2F
推
02/05 23:20, , 3F
02/05 23:20, 3F
→
02/06 19:32, , 4F
02/06 19:32, 4F
→
02/06 19:32, , 5F
02/06 19:32, 5F
→
02/06 19:33, , 6F
02/06 19:33, 6F
推
02/06 22:17, , 7F
02/06 22:17, 7F
推
02/06 22:38, , 8F
02/06 22:38, 8F
→
02/06 22:38, , 9F
02/06 22:38, 9F
推
02/07 04:20, , 10F
02/07 04:20, 10F
→
02/07 04:20, , 11F
02/07 04:20, 11F
→
02/07 12:16, , 12F
02/07 12:16, 12F
→
02/07 12:17, , 13F
02/07 12:17, 13F
→
02/07 12:20, , 14F
02/07 12:20, 14F
推
02/07 23:11, , 15F
02/07 23:11, 15F
→
02/07 23:11, , 16F
02/07 23:11, 16F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30