最近在看一些资料结构的资料，我发现网络上有不少人讨论 "主席树"
可以拿来作区间第 k 大 + 修改
有人知道这到底是什么东西吗？ 我是指学术上的名字
感觉好像是一群segment tree..
概念跟persistence segment tree很像 http://ppt.cc/f6h3
还是根本是同一个东西??

同一个东西中国资讯封闭 小朋友自己发明新名称

那请问有人知道 莫队算法 的英文是什么吗？

莫队算法，是大陆人莫涛所属的队伍想到的。大概没英文找大陆国家选训的投影片，某一年中有他说明的简报

原来 "莫队" 做此解阿WWW

可不可以简单介绍一下莫队算法的功用啊？

莫队必须离线询问，完成区间查找。概念类似块状链表查找性质必须符合 [l,r] 转移 [l,r+1],[l-1,r] 都是快于 O(n)，这样复杂度会是 O(n^1.5 * f(n))解决一般 RMQ 相关资料结构无法解决的询问网络上给的例题 区间众数 区间相同数期望值 ... 等

区间众数 是类似这样吗？ http://ppt.cc/UN~d

是，你给的那个做法有根据性质特化，效率比莫队好且可以变成在线算法，但是莫队的精神在于移动左右端点根据分块策略慢慢推动左右端点回答所有询问。

http://www.zhihu.com/question/26547156莫涛的回文，请点选一下评论，里面Chao Xu有考察这个算法。顺便一提OIer提到的“线段树”不是学术界的segment tree个人研判“线段树”其实是quadtree的一维版本

我觉得他们说的线段树 比较像是一维的range tree其实这样讲也不太精确 因为我们没定义他们说的 "线段树"到底是什么？

http://ppt.cc/m3t0 Mars Maps (top-down version)http://www.slideshare.net/DanielChou/ss-7792670 (btm-up)然后一维的情况下 range tree/kd tree/quadtree 好像都一样

那应该就像你说的 是类似 1D 的 partition treehttp://blog.csdn.net/wxjlzbcd/article/details/43602195附带问一下 有人把这些论文都看完的吗？我觉得差别应该是在 是怎么切分吧range tree 是从插入元素的中位数来切但是他们说的线段数 是按照元素的范围的中位数来切不过差别不是那么的大就是了..

提到 1D partition tree 的期刊论文是哪一篇？

不知道..有人知道 CDQ分治 学术上叫做什么吗？