[問題] 主席樹？

[FRAXIS (喔喔)]

最近在看一些資料結構的資料，我發現網路上有不少人討論 "主席樹"

可以拿來作區間第 k 大 + 修改

有人知道這到底是什麼東西嗎？ 我是指學術上的名字

感覺好像是一群segment tree..

概念跟persistence segment tree很像 http://ppt.cc/f6h3

還是根本是同一個東西??

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.133.134.181
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422920348.A.674.html
推 DJWS: 同一個東西
→ DJWS: 中國資訊封閉  小朋友自己發明新名稱
推 johnathan717: 那請問有人知道 莫队算法 的英文是什麼嗎？
推 Morris1028: 莫隊算法，是大陸人莫濤所屬的隊伍想到的。大概沒英文
→ Morris1028: 找大陸國家選訓的投影片，某一年中有他說明的簡報
推 suhorng: 原來 "莫隊" 做此解阿WWW
→ FRAXIS: 可不可以簡單介紹一下莫隊算法的功用啊？
推 Morris1028: 莫隊必須離線詢問，完成區間查找。概念類似塊狀鏈表
→ Morris1028: 查找性質必須符合 [l,r] 轉移 [l,r+1],[l-1,r] 都是
→ Morris1028: 快於 O(n)，這樣複雜度會是 O(n^1.5 * f(n))
→ Morris1028: 解決一般 RMQ 相關資料結構無法解決的詢問
→ Morris1028: 網路上給的例題 區間眾數 區間相同數期望值 ... 等
→ FRAXIS: 區間眾數 是類似這樣嗎？ http://ppt.cc/UN~d
推 Morris1028: 是，你給的那個做法有根據性質特化，效率比莫隊好
→ Morris1028: 且可以變成在線算法，但是莫隊的精神在於移動左右端點
→ Morris1028: 根據分塊策略慢慢推動左右端點回答所有詢問。
推 DJWS: http://www.zhihu.com/question/26547156
→ DJWS: 莫濤的回文，請點選一下評論，裡面Chao Xu有考察這個算法。
→ DJWS: 順便一提OIer提到的「線段樹」不是學術界的segment tree
→ DJWS: 個人研判「線段樹」其實是quadtree的一維版本
→ FRAXIS: 我覺得他們說的線段樹 比較像是一維的range tree
→ FRAXIS: 其實這樣講也不太精確 因為我們沒定義他們說的 "線段樹"
→ FRAXIS: 到底是什麼？
推 DJWS: http://ppt.cc/m3t0   Mars Maps  (top-down version)
→ DJWS: http://www.slideshare.net/DanielChou/ss-7792670 (btm-up)
→ DJWS: 然後一維的情況下 range tree/kd tree/quadtree 好像都一樣
→ FRAXIS: 那應該就像你說的 是類似 1D 的 partition tree
→ FRAXIS: http://blog.csdn.net/wxjlzbcd/article/details/43602195
→ FRAXIS: 附帶問一下 有人把這些論文都看完的嗎？
→ FRAXIS: 我覺得差別應該是在 是怎麼切分吧
→ FRAXIS: range tree 是從插入元素的中位數來切
→ FRAXIS: 但是他們說的線段數 是按照元素的範圍的中位數來切
→ FRAXIS: 不過差別不是那麼的大就是了..
推 DJWS: 提到 1D partition tree 的期刊論文是哪一篇？
→ FRAXIS: 不知道..
→ FRAXIS: 有人知道 CDQ分治 學術上叫做什麼嗎？