作者:
flere (人間失格)
2014-11-06 17:44:19標題不知道下的好不好..> <
問題:
一棵N個點的tree
接下來有許多操作, 操作共有兩種:
1. 把一個無色的點上色, 或是把一個上色的點變成無色
2. 給一個點v, 輸出v到root路徑裡所有上色的點編號
請問有相關的paper或是關鍵字嗎?
還是已經有某個資料結構支援這個問題了??
謝謝大家!!
作者:
yr (Sooner Born Sooner Bred)
2014-11-06 18:45:00看起來 DFS 就可以做到，有其他限制嗎？2? 所以是 binary tree ? 除非你這樹有什麼特性，不然一般最差就是 O(n) ，題目並沒有提到任何特性啊加一個到 parent 的指標，然後用 hash table 存每個點？
作者: fenzhang (分帳) 2014-11-06 19:57:00
樹鍊剖分套BIT套SET
作者: ferng1021 (菘~~~) 2014-11-06 21:26:00
(2) 要輸出每一個點的編號就 O(n) 了
作者: paae0226 (paae0226) 2014-11-06 22:43:00
是 kerker 耶 所以這是要 online?
作者:
yr (Sooner Born Sooner Bred)
2014-11-06 22:59:00(2) 最差就 O(h) ，而 O(h) 最差是 O(n)如果樹可以改成 self-balancing binary tree 才能 O(logn)
作者: paae0226 (paae0226) 2014-11-06 23:08:00
想了一下還是推 5 樓 f 大 不過好像有 3 個 log 就是
作者: esrever 2014-11-07 01:22:00
splay tree 似乎可以做到 amortized O(logn)欸不對 不能用 splay tree，它會改變樹形...
作者:
stimim (qqaa)
2014-11-07 19:48:00link-cut tree, heavy-light decomposition 應該都可以用如果要輸出編號而不是數量的話，那一定會到 O(n) 不是嗎？假如把所有的點都上色，每次都query最遠的那個點
作者: fenzhang (分帳) 2014-11-07 22:25:00
離線做可以把所有點存在的時間區間弄出來，之後邊DFS邊維護線段數套SET可以做到修改均攤lg^2查詢均攤lg+occ