最近在看一些資料結構的資料，我發現網路上有不少人討論 "主席樹"
可以拿來作區間第 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分治 學術上叫做什麼嗎？