[问题] dynamic tree, query path flere PTT批踢踢实业坊

[问题] dynamic tree, query path

楼主: 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) 了

作者: singlovesong (~"~) 2014-11-06 21:28:00

但是也许可以amortized

作者: 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，它会改变树形...

作者: DJWS (...) 2014-11-07 13:37:00

问这些人 http://ppt.cc/ZSvz 不过我估计台湾没人能回答你

作者: stimim (qqaa) 2014-11-07 19:48:00

link-cut tree, heavy-light decomposition 应该都可以用如果要输出编号而不是数量的话，那一定会到 O(n) 不是吗？假如把所有的点都上色，每次都query最远的那个点

作者: fenzhang (分帐) 2014-11-07 22:25:00

离线做可以把所有点存在的时间区间弄出来，之后边DFS边维护线段数套SET可以做到修改均摊lg^2查询均摊lg+occ

继续阅读

[问题] quicksort on peaked array jb679123 [问题] Re: [问题] 0～9 挑k个数字, 组出最接近 kather Re: [问题] 0～9 挑k个数字, 组出最接近 A 的数字bleed1979 Re: [问题] 0～9 挑k个数字, 组出最接近 A 的数字flere Re: [问题] 0～9 挑k个数字, 组出最接近 A 的数字bleed1979 Re: [问题] 0～9 挑k个数字, 组出最接近 A 的数字EdisonX [问题] 0～9 挑k个数字, 组出最接近 A 的数字ooooooo Re: [问题] decision tree高度yr [问题] decision tree高度jb679123 [问题] 平面上 N 点，放额外一点 P 求最近点EdisonX