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