Segment Tree
#Sequences #SegmentTree
Operations
モノイド$ Mの列$ (a_1, a_2, \dots, a_n)を扱う.
空間計算量$ \Theta(n)
$ \mathtt{new}()
列の項がすべて$ Mの単位元であるSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{build}(a_1, a_2, \dots, a_n)
与えられた列を表現するSegment Treeを作成する.
時間計算量$ \Theta(n)
$ \mathtt{set}(i, x)
$ a_iに$ xを代入する.
時間計算量$ \Omicron(\log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l+1} \cdot \dots \cdot a_rを計算する.
時間計算量$ \Omicron(\log n)
Summary
https://gyazo.com/928b1fdc99b7000a0946c92fc33878bc
列のすべての区間をたかだか$ \log n個の重ならない区間に分割する
$ \mathtt{set}
https://gyazo.com/8699ae544f20c9552678904629a7c6db
$ \mathtt{fold}
https://gyazo.com/d4d963706b405f0dc456df884b638099
References
セグメント木をソラで書きたいあなたに
SlideShare: プログラミングコンテストでのデータ構造
Segment Treeをちょっと高速化したい
ちょっと変わったセグメント木の使い方
Notes
添字は0-based, 1-basedの2通り
考えているノード番号を$ iとする
0-based
配列の長さ: $ 2N - 1 ($ Nは$ n < Nとなる2冪の数)
親: $ (i - 1) / 2
右の子: $ 2i + 1
左の子: $ 2i + 2
$ k番目の葉: $ k + N - 1
1-based
配列の長さ: $ 2N ($ Nは$ n < Nとなる2冪の数)
親: $ i / 2
右の子: $ 2i
左の子: $ 2i + 1
$ k番目の葉: $ k + N
$ \mathtt{fold}を非再帰で書く方法がある.
定数倍が軽い
1-basedがおすすめ
$ \Omicron(\log n)で列を二分探索できる.
配列の長さを$ 2nにする実装が存在する (非再帰, 1-based)
Implementations
再帰
C++: Segment Tree - Algoogle
非再帰
C++: Segment-Tree | Luzhiled's memo
Rust: rust-data-structures/segment_tree.rs at master - niuez/rust-data-structures
Problems
https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_E
imos法