PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] dynamic tree, query path

看板Prob_Solve (計算數學 Problem Solving)作者 (人間失格)時間10年前 (2014/11/06 17:44), 10年前編輯推噓8(8推 0噓 11→)
留言19則, 8人參與, 最新討論串1/1
標題不知道下的好不好..> < 問題: 一棵N個點的tree 接下來有許多操作, 操作共有兩種: 1. 把一個無色的點上色, 或是把一個上色的點變成無色 2. 給一個點v, 輸出v到root路徑裡所有上色的點編號 請問有相關的paper或是關鍵字嗎? 還是已經有某個資料結構支援這個問題了?? 謝謝大家!! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.236.49.74 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1415267062.A.B5C.html ※ 編輯: flere (119.236.49.74), 11/06/2014 17:44:38
→
11/06 18:45, , 1F
看起來 DFS 就可以做到，有其他限制嗎？
11/06 18:45, 1F
DFS? 沒有特別處理對於操作二的話 最差會到O(N)喔! ※ 編輯: flere (119.236.49.74), 11/06/2014 18:53:57
→
11/06 18:58, , 2F
2? 所以是 binary tree ? 除非你這樹有什麼特性，不然
11/06 18:58, 2F
→
11/06 18:59, , 3F
一般最差就是 O(n) ，題目並沒有提到任何特性啊
11/06 18:59, 3F
呃我就是想問看看能不能對樹進行改造讓兩個操作都能很快.. 比如說樹鏈剖分, 對每條鏈套其他資料結構.. ※ 編輯: flere (119.236.49.74), 11/06/2014 19:04:46
→
11/06 19:10, , 4F
加一個到 parent 的指標，然後用 hash table 存每個點？
11/06 19:10, 4F
推
11/06 19:57, , 5F
樹鍊剖分套BIT套SET
11/06 19:57, 5F
→
11/06 21:26, , 6F
(2) 要輸出每一個點的編號就 O(n) 了
11/06 21:26, 6F
推
11/06 21:28, , 7F
但是也許可以amortized
11/06 21:28, 7F
大部分我們在估複雜度的時候 會把輸出的部分變成occurence來看 所以可以變成O(logn + occ)之類的沒有問題~ ※ 編輯: flere (119.236.49.74), 11/06/2014 21:49:56
推
11/06 22:43, , 8F
是 kerker 耶 所以這是要 online?
11/06 22:43, 8F
→
11/06 22:59, , 9F
(2) 最差就 O(h) ，而 O(h) 最差是 O(n)
11/06 22:59, 9F
→
11/06 23:00, , 10F
如果樹可以改成 self-balancing binary tree 才能 O(logn)
11/06 23:00, 10F
推
11/06 23:08, , 11F
想了一下還是推 5 樓 f 大 不過好像有 3 個 log 就是
11/06 23:08, 11F
推
11/07 01:22, , 12F
splay tree 似乎可以做到 amortized O(logn)
11/07 01:22, 12F
→
11/07 02:12, , 13F
欸不對 不能用 splay tree，它會改變樹形...
11/07 02:12, 13F
推
11/07 13:37, , 14F
問這些人 http://ppt.cc/ZSvz 不過我估計台灣沒人能回答你
11/07 13:37, 14F
推
11/07 19:48, , 15F
link-cut tree, heavy-light decomposition 應該都可以用
11/07 19:48, 15F
→
11/07 19:53, , 16F
如果要輸出編號而不是數量的話，那一定會到 O(n) 不是嗎？
11/07 19:53, 16F
→
11/07 19:53, , 17F
假如把所有的點都上色，每次都query最遠的那個點
11/07 19:53, 17F
把上面的想法拿掉好了XD 總之用tree decomposition必定能解 很多算法的複雜度估算都會使用output sensitive 也就是我的複雜度除了output的時間外希望能越快越好 比如說O(logn+occurence) 這樣即使occurence是0也只會花到最多O(logn) 但如果是直接走回root看結果的話 就必定O(n)了 ※ 編輯: flere (119.236.49.74), 11/07/2014 20:29:37
推
11/07 22:25, , 18F
離線做可以把所有點存在的時間區間弄出來，之後邊DFS邊
11/07 22:25, 18F
→
11/07 22:28, , 19F
維護線段數套SET可以做到修改均攤lg^2查詢均攤lg+occ
11/07 22:28, 19F
‣ 更多 flere 的文章
文章代碼(AID): #1KMqBsjS (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 flere 的文章
文章代碼(AID): #1KMqBsjS (Prob_Solve)