創作內容

4 GP

【程式碼】1D Fake Segment tree

作者:♙♲⚙\~O_O~/⚙♲♙│2021-06-08 13:25:14│巴幣:8│人氣:84
segment tree:
https://en.wikipedia.org/wiki/Segment_tree

簡單介紹 segment tree

用途:
你現在有個運算子,有結合律,例如 乘(*) 或 取大(max)。
以及一個陣列內含一堆元素,例如一堆大小一樣的方形矩陣。
線段樹讓你在 O(lg(n)) 的時間內執行下列其1:
1. 更新一個元素
2. 詢問某個區間之間的各個元素之間,使用前面提到的運算子算完的結果
3. O(lg(n)) 的 stack push 或 stack pop (我多做的)

形狀:
binary tree
但下列的實作是lg(n)條陣列
// n 為元素數量

空間複雜度需求:
額外 O(n)
// n 為元素數量

懶人包:
O(m) 時間的事情在預先處理後,以後要花的時間壓到 O(lg(n)) 時間,並且空間要另外 O(n)
// n 為元素數量 ; m 為區間長度


模板

c++
https://gist.github.com/aaaaagold/b33db9de95eccbfe19d4a856ee8af222

javascript
https://gist.github.com/aaaaagold/7367b59d842dd66eb57f2d73bc7db1c8

概要使用注意事項:
先看 constructor ,可以注意到不管哪個版本都有一個參數叫做 op ,此為 operator  ;以及一個參數叫做 initVal ,此為 op 的 Identity ,即任何元素e與此值使用 op 運算後,值仍為原本的元素e

建樹概觀:
從底下(較少元素)兩兩節點往上
也因為是 children 決定 parent node ,而不是 parent node 決定 children ,所以可以做出 O(lg(n)) 的 stack push 和 stack pop 。
// n 為元素數量




延伸閱讀A (我不會這個,不要問我,我只是在 wiki 看到它)
https://en.wikipedia.org/wiki/Fenwick_tree

延伸閱讀B (以前寫的,有提到segment tree)
https://home.gamer.com.tw/creationDetail.php?sn=3960915
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=5172186
Some rights reserved. 姓名標示-非商業性 2.5 台灣

相關創作

同標籤作品搜尋:Segment tree|線段樹|演算法

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

4喜歡★agold404 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:我該不該開放RMMV的插... 後一篇:【RMMV】plugin...

追蹤私訊切換新版閱覽

作品資料夾

huaing123垃圾留言
就是這堆層出不窮的垃圾留言,逼人不得不開始做出些連自己都厭惡的"應對"呢......看更多我要大聲說昨天20:12


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】