作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 主席树？
时间Tue Feb 3 07:39:05 2015
最近在看一些资料结构的资料，我发现网路上有不少人讨论 "主席树"
可以拿来作区间第 k 大 + 修改
有人知道这到底是什麽东西吗？ 我是指学术上的名字
感觉好像是一群segment tree..
概念跟persistence segment tree很像
http://ppt.cc/f6h3
还是根本是同一个东西??
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 50.133.134.181
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1422920348.A.674.html
1F：推 DJWS: 同一个东西 02/03 10:15
2F：→ DJWS: 中国资讯封闭 小朋友自己发明新名称 02/03 10:17
3F：推 johnathan717: 那请问有人知道 莫队算法 的英文是什麽吗？ 02/04 11:32
4F：推 Morris1028: 莫队算法，是大陆人莫涛所属的队伍想到的。大概没英文 02/04 12:27
5F：→ Morris1028: 找大陆国家选训的投影片，某一年中有他说明的简报 02/04 12:28
6F：推 suhorng: 原来 "莫队" 做此解阿WWW 02/05 00:18
7F：→ FRAXIS: 可不可以简单介绍一下莫队算法的功用啊？ 02/05 01:26
8F：推 Morris1028: 莫队必须离线询问，完成区间查找。概念类似块状链表 02/05 08:05
9F：→ Morris1028: 查找性质必须符合 [l,r] 转移 [l,r+1],[l-1,r] 都是 02/05 08:07
10F：→ Morris1028: 快於 O(n)，这样复杂度会是 O(n^1.5 * f(n)) 02/05 08:08
11F：→ Morris1028: 解决一般 RMQ 相关资料结构无法解决的询问 02/05 08:10
12F：→ Morris1028: 网路上给的例题 区间众数 区间相同数期望值 ... 等 02/05 08:13
14F：推 Morris1028: 是，你给的那个做法有根据性质特化，效率比莫队好 02/05 11:55
15F：→ Morris1028: 且可以变成在线算法，但是莫队的精神在於移动左右端点 02/05 12:09
16F：→ Morris1028: 根据分块策略慢慢推动左右端点回答所有询问。 02/05 12:10
18F：→ DJWS: 莫涛的回文，请点选一下评论，里面Chao Xu有考察这个算法。 02/10 11:37
19F：→ DJWS: 顺便一提OIer提到的「线段树」不是学术界的segment tree 02/10 11:38
20F：→ DJWS: 个人研判「线段树」其实是quadtree的一维版本 02/10 11:39
21F：→ FRAXIS: 我觉得他们说的线段树 比较像是一维的range tree 02/10 22:06
22F：→ FRAXIS: 其实这样讲也不太精确 因为我们没定义他们说的 "线段树" 02/10 22:17
23F：→ FRAXIS: 到底是什麽？ 02/10 22:17
26F：→ DJWS: 然後一维的情况下 range tree/kd tree/quadtree 好像都一样 02/11 13:08
27F：→ FRAXIS: 那应该就像你说的 是类似 1D 的 partition tree 02/11 22:42
29F：→ FRAXIS: 附带问一下 有人把这些论文都看完的吗？ 02/11 22:43
30F：→ FRAXIS: 我觉得差别应该是在 是怎麽切分吧 02/11 22:45
31F：→ FRAXIS: range tree 是从插入元素的中位数来切 02/11 22:45
32F：→ FRAXIS: 但是他们说的线段数 是按照元素的范围的中位数来切 02/11 22:46
33F：→ FRAXIS: 不过差别不是那麽的大就是了.. 02/11 22:47
34F：推 DJWS: 提到 1D partition tree 的期刊论文是哪一篇？ 02/12 10:27
35F：→ FRAXIS: 不知道.. 02/12 22:02
36F：→ FRAXIS: 有人知道 CDQ分治 学术上叫做什麽吗？ 02/12 22:18