4 GP
【程式碼】1D Fake Segment tree
作者：♙♲⚙＼~O_O~／⚙♲♙│2021-06-08 13:25:14│巴幣：8│人氣：209
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 台灣
創作內容
leetcode (7)
