看板 [ Prob_Solve ]
討論串[問題] 主席樹？
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 主席樹？
推噓9(9推 0噓 27→)留言36則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/02/03 07:39), 編輯資訊
1
0
1
內容預覽:
最近在看一些資料結構的資料，我發現網路上有不少人討論 "主席樹". 可以拿來作區間第 k 大 + 修改. 有人知道這到底是什麼東西嗎？ 我是指學術上的名字. 感覺好像是一群segment tree... 概念跟persistence segment tree很像 http://ppt.cc/f6h3
#2
Re: [問題] 主席樹？
推噓7(7推 0噓 9→)留言16則，0人參與, 最新作者DJWS (...)時間9年前 (2015/02/05 13:46), 9年前編輯資訊
0
0
0
內容預覽:
現在有許多個區間查詢 Q = { [a1,b1] , [a2,b2] , ... , [ak,bk] }. 預計其查詢結果是 r[a1,b1] ... r[ak,bk]. 假設問題具備此性質：. 已知 r[a,b] ，可以快速求得邊界差一的結果如 r[a-1,b] r[a+1,b] r[a,b-1]
(還有393個字)
#3
Re: [問題] 主席樹？
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/02/06 01:17), 9年前編輯資訊
0
0
1
內容預覽:
我這幾天稍微看了一下區間第 k 大，不知道自己想的對不對，. 上來跟大家討論一下。 （不好意思這篇很長）. 題目是這樣： 給定 n 個整數的陣列 A，以及 m 個查詢 [lj, rj], kj. 找出 A[lj..rj] 的第 k 大數字. http://ppt.cc/24oD 這邊是 wiki 的
(還有2560個字)
#4
Re: [問題] 主席樹？
推噓0(0推 0噓 2→)留言2則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/02/07 23:47), 9年前編輯資訊
0
0
0
內容預覽:
我研究了一下，如果元素有 n 個，查詢有 m 個，當 m 至少為 n^0.5，. 莫隊算法那空間複雜度應該會是 O((n+m) * n^0.5 * (狀態轉移cost) + 排序). 空間是 O(m+狀態表示)。. 所以我猜主要的優勢是在好實作和省空間吧。. 我嘗試了幾個題目（假設m = O(n)）
(還有718個字)
首頁
上一頁
1
下一頁
尾頁