作者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/cn.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