作者flere (人間失格)
站內Prob_Solve
標題[問題] dynamic tree, query path
時間Thu Nov 6 17:44:19 2014
標題不知道下的好不好..> <
問題:
一棵N個點的tree
接下來有許多操作, 操作共有兩種:
1. 把一個無色的點上色, 或是把一個上色的點變成無色
2. 給一個點v, 輸出v到root路徑裡所有上色的點編號
請問有相關的paper或是關鍵字嗎?
還是已經有某個資料結構支援這個問題了??
謝謝大家!!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.236.49.74
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1415267062.A.B5C.html
※ 編輯: flere (119.236.49.74), 11/06/2014 17:44:38
1F：→ yr: 看起來 DFS 就可以做到，有其他限制嗎？ 11/06 18:45
DFS?
沒有特別處理對於操作二的話
最差會到O(N)喔!
※ 編輯: flere (119.236.49.74), 11/06/2014 18:53:57
2F：→ yr: 2? 所以是 binary tree ? 除非你這樹有什麼特性，不然 11/06 18:58
3F：→ yr: 一般最差就是 O(n) ，題目並沒有提到任何特性啊 11/06 18:59
呃我就是想問看看能不能對樹進行改造讓兩個操作都能很快..
比如說樹鏈剖分, 對每條鏈套其他資料結構..
※ 編輯: flere (119.236.49.74), 11/06/2014 19:04:46
4F：→ yr: 加一個到 parent 的指標，然後用 hash table 存每個點？ 11/06 19:10
5F：推 fenzhang: 樹鍊剖分套BIT套SET 11/06 19:57
6F：→ ferng1021: (2) 要輸出每一個點的編號就 O(n) 了 11/06 21:26
7F：推 singlovesong: 但是也許可以amortized 11/06 21:28
大部分我們在估複雜度的時候
會把輸出的部分變成occurence來看
所以可以變成O(logn + occ)之類的沒有問題~
※ 編輯: flere (119.236.49.74), 11/06/2014 21:49:56
8F：推 paae0226: 是 kerker 耶 所以這是要 online? 11/06 22:43
9F：→ yr: (2) 最差就 O(h) ，而 O(h) 最差是 O(n) 11/06 22:59
10F：→ yr: 如果樹可以改成 self-balancing binary tree 才能 O(logn) 11/06 23:00
11F：推 paae0226: 想了一下還是推 5 樓 f 大 不過好像有 3 個 log 就是 11/06 23:08
12F：推 esrever: splay tree 似乎可以做到 amortized O(logn) 11/07 01:22
13F：→ esrever: 欸不對 不能用 splay tree，它會改變樹形... 11/07 02:12
15F：推 stimim: link-cut tree, heavy-light decomposition 應該都可以用 11/07 19:48
16F：→ stimim: 如果要輸出編號而不是數量的話，那一定會到 O(n) 不是嗎？ 11/07 19:53
17F：→ stimim: 假如把所有的點都上色，每次都query最遠的那個點 11/07 19:53
把上面的想法拿掉好了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
18F：推 fenzhang: 離線做可以把所有點存在的時間區間弄出來，之後邊DFS邊 11/07 22:25
19F：→ fenzhang: 維護線段數套SET可以做到修改均攤lg^2查詢均攤lg+occ 11/07 22:28