【程式碼】1D Fake Segment tree

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

LINE 分享

小屋創作

日誌2021-06-08 13:25
【程式碼】1D Fake Segment tree

相關創作

【筆記】學著一步一步將一堆迴圈拆掉

〈都是演算法惹的禍〉

[達人專欄] 感謝每位在FB還看的見仙人掌貼文，並給於支持的你

留言

日誌2021-06-08 13:25【程式碼】1D Fake Segment tree

相關創作

【筆記】學著一步一步將一堆迴圈拆掉

〈都是演算法惹的禍〉

[達人專欄] 感謝每位在FB還看的見仙人掌貼文，並給於支持的你

留言

日誌2021-06-08 13:25
【程式碼】1D Fake Segment tree