PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 主席樹？

看板Prob_Solve (計算數學 Problem Solving)作者 (喔喔)時間9年前 (2015/02/03 07:39), 編輯推噓9(9推 0噓 27→)
留言36則, 5人參與, 最新討論串1/4 (看更多)
最近在看一些資料結構的資料，我發現網路上有不少人討論 "主席樹" 可以拿來作區間第 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
推
02/03 10:15, , 1F
同一個東西
02/03 10:15, 1F
→
02/03 10:17, , 2F
中國資訊封閉 小朋友自己發明新名稱
02/03 10:17, 2F
推
02/04 11:32, , 3F
那請問有人知道 莫队算法 的英文是什麼嗎？
02/04 11:32, 3F
推
02/04 12:27, , 4F
莫隊算法，是大陸人莫濤所屬的隊伍想到的。大概沒英文
02/04 12:27, 4F
→
02/04 12:28, , 5F
找大陸國家選訓的投影片，某一年中有他說明的簡報
02/04 12:28, 5F
推
02/05 00:18, , 6F
原來 "莫隊" 做此解阿WWW
02/05 00:18, 6F
→
02/05 01:26, , 7F
可不可以簡單介紹一下莫隊算法的功用啊？
02/05 01:26, 7F
推
02/05 08:05, , 8F
莫隊必須離線詢問，完成區間查找。概念類似塊狀鏈表
02/05 08:05, 8F
→
02/05 08:07, , 9F
查找性質必須符合 [l,r] 轉移 [l,r+1],[l-1,r] 都是
02/05 08:07, 9F
→
02/05 08:08, , 10F
快於 O(n)，這樣複雜度會是 O(n^1.5 * f(n))
02/05 08:08, 10F
→
02/05 08:10, , 11F
解決一般 RMQ 相關資料結構無法解決的詢問
02/05 08:10, 11F
→
02/05 08:13, , 12F
網路上給的例題 區間眾數 區間相同數期望值 ... 等
02/05 08:13, 12F
→
02/05 08:48, , 13F
區間眾數 是類似這樣嗎？ http://ppt.cc/UN~d
02/05 08:48, 13F
推
02/05 11:55, , 14F
是，你給的那個做法有根據性質特化，效率比莫隊好
02/05 11:55, 14F
→
02/05 12:09, , 15F
且可以變成在線算法，但是莫隊的精神在於移動左右端點
02/05 12:09, 15F
→
02/05 12:10, , 16F
根據分塊策略慢慢推動左右端點回答所有詢問。
02/05 12:10, 16F
推
02/10 11:36, , 17F
02/10 11:36, 17F
→
02/10 11:37, , 18F
莫濤的回文，請點選一下評論，裡面Chao Xu有考察這個算法。
02/10 11:37, 18F
→
02/10 11:38, , 19F
順便一提OIer提到的「線段樹」不是學術界的segment tree
02/10 11:38, 19F
→
02/10 11:39, , 20F
個人研判「線段樹」其實是quadtree的一維版本
02/10 11:39, 20F
→
02/10 22:06, , 21F
我覺得他們說的線段樹 比較像是一維的range tree
02/10 22:06, 21F
→
02/10 22:17, , 22F
其實這樣講也不太精確 因為我們沒定義他們說的 "線段樹"
02/10 22:17, 22F
→
02/10 22:17, , 23F
到底是什麼？
02/10 22:17, 23F
推
02/11 13:04, , 24F
http://ppt.cc/m3t0 Mars Maps (top-down version)
02/11 13:04, 24F
→
02/11 13:05, , 25F
02/11 13:05, 25F
→
02/11 13:08, , 26F
然後一維的情況下 range tree/kd tree/quadtree 好像都一樣
02/11 13:08, 26F
→
02/11 22:42, , 27F
那應該就像你說的 是類似 1D 的 partition tree
02/11 22:42, 27F
→
02/11 22:43, , 29F
附帶問一下 有人把這些論文都看完的嗎？
02/11 22:43, 29F
→
02/11 22:45, , 30F
我覺得差別應該是在 是怎麼切分吧
02/11 22:45, 30F
→
02/11 22:45, , 31F
range tree 是從插入元素的中位數來切
02/11 22:45, 31F
→
02/11 22:46, , 32F
但是他們說的線段數 是按照元素的範圍的中位數來切
02/11 22:46, 32F
→
02/11 22:47, , 33F
不過差別不是那麼的大就是了..
02/11 22:47, 33F
推
02/12 10:27, , 34F
提到 1D partition tree 的期刊論文是哪一篇？
02/12 10:27, 34F
→
02/12 22:02, , 35F
不知道..
02/12 22:02, 35F
→
02/12 22:18, , 36F
有人知道 CDQ分治 學術上叫做什麼嗎？
02/12 22:18, 36F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1Kq0gSPq (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
7
16
Re: [問題] 主席樹？
DJWS
9年前, 02/05
完整討論串 (本文為第 1 之 4 篇)：
排序： 最舊先 | 最新先 | 留言數
9
36
[問題] 主席樹？
FRAXIS
9年前, 02/03
7
16
Re: [問題] 主席樹？
DJWS
9年前, 02/05
在新視窗開啟完整討論串 (共4篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1Kq0gSPq (Prob_Solve)