セグメント木 (segment tree)
(include/emthrm/data_structure/segment_tree.hpp)
セグメント木 (segment tree)
モノイドであるデータに対して高速に区間クエリを処理する(完全)二分木である。
時間計算量
$\langle O(N), O(\log{N}) \rangle$
仕様
セグメント木
template <typename T>
requires requires {
typename T::Monoid;
{T::id()} -> std::same_as<typename T::Monoid>;
{T::merge(std::declval<typename T::Monoid>(),
std::declval<typename T::Monoid>())}
-> std::same_as<typename T::Monoid>;
}
struct SegmentTree;
-
T
:モノイドを表す構造体であり、以下の型エイリアスと静的メンバ関数を必要とする。
-
Monoid
:要素型
-
static constexpr Monoid id();
:単位元
-
static Monoid merge(const Monoid&, const Monoid&);
:二項演算 $\circ$
メンバ関数
名前 |
効果・戻り値 |
explicit SegmentTree(const int n); |
要素数 $N$ のオブジェクトを構築する。 |
explicit SegmentTree(const std::vector<Monoid>& a); |
$A$ に対してオブジェクトを構築する。 |
void set(int idx, const Monoid val); |
$A_{\mathrm{idx}} \gets \mathrm{val}$ |
Monoid get(int left, int right) const; |
$A_{\mathrm{left}} \circ \cdots \circ A_{\mathrm{right}}$ |
Monoid operator[](const int idx) const; |
$A_{\mathrm{idx}}$ |
template <typename G>
int find_right(int left, const G g);
|
g(get(left, right + 1)) = false を満たす最小の $\mathrm{right}$。ただし存在しないときは $N$ を返す。 |
template <typename G>
int find_left(int right, const G g);
|
g(get(left, right)) = false を満たす最大の $\mathrm{left}$。ただし存在しないときは $-1$ を返す。 |
メンバ型
遅延伝播セグメント木
template <typename T>
requires requires {
typename T::Monoid;
typename T::OperatorMonoid;
{T::m_id()} -> std::same_as<typename T::Monoid>;
{T::o_id()} -> std::same_as<typename T::OperatorMonoid>;
{T::m_merge(std::declval<typename T::Monoid>(),
std::declval<typename T::Monoid>())}
-> std::same_as<typename T::Monoid>;
{T::o_merge(std::declval<typename T::OperatorMonoid>(),
std::declval<typename T::OperatorMonoid>())}
-> std::same_as<typename T::OperatorMonoid>;
{T::apply(std::declval<typename T::Monoid>(),
std::declval<typename T::OperatorMonoid>())}
-> std::same_as<typename T::Monoid>;
}
struct LazySegmentTree;
-
T
:モノイドを表す構造体であり、以下の型エイリアスと静的メンバ関数を必要とする。
-
Monoid
:要素型
-
OperatorMonoid
:作用素モノイドの要素型
-
static constexpr Monoid m_id();
:単位元
-
static constexpr OperatorMonoid o_id();
:作用素モノイドの単位元
-
static Monoid m_merge(const Monoid&, const Monoid&);
:二項演算 $\circ$
static OperatorMonoid o_merge(const OperatorMonoid&, const OperatorMonoid&);
static Monoid apply(const Monoid&, const OperatorMonoid&);
メンバ関数
名前 |
効果・戻り値 |
explicit LazySegmentTree(const int n); |
要素数 $N$ のオブジェクトを構築する。 |
explicit LazySegmentTree(const std::vector<Monoid>& a); |
$A$ に対してオブジェクトを構築する。 |
void set(int idx, const Monoid val); |
$A_{\mathrm{idx}} \gets \mathrm{val}$ |
void apply(int idx, const OperatorMonoid val); |
$\mathrm{idx}$ における変更クエリ |
void apply(int left, int right, const OperatorMonoid val); |
$[\mathrm{left}, \mathrm{right})$ における変更クエリ |
Monoid get(int left, int right); |
$[\mathrm{left}, \mathrm{right})$ における解答クエリ |
Monoid operator[](const int idx); |
$A_{\mathrm{idx}}$ |
template <typename G>
int find_right(int left, const G g);
|
g(get(left, right + 1)) = false を満たす最小の $\mathrm{right}$。ただし存在しない場合は $N$ を返す。 |
template <typename G>
int find_left(int right, const G g);
|
g(get(left, right)) = false を満たす最大の $\mathrm{left}$。ただし存在しない場合は $-1$ を返す。 |
メンバ型
名前 |
説明 |
Monoid |
T::Monoid |
OperatorMonoid |
T::OperatorMonoid |
参考文献
- https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
- https://beet-aizu.hatenablog.com/entry/2019/11/27/125906
- http://kagamiz.hatenablog.com/entry/2012/12/18/220849
- https://kmyk.github.io/blog/blog/2020/03/04/segment-tree-is-not-complete-binary-tree/
セグメント木
- https://tsutaj.hatenablog.com/entry/2017/03/29/204841
- https://github.com/atcoder/ac-library/blob/8de49c6f150d2e5af851cbbd074aee552bf2bec9/atcoder/segtree.hpp
遅延伝播セグメント木
- https://tsutaj.hatenablog.com/entry/2017/03/30/224339
- https://kazuma8128.hatenablog.com/entry/2017/12/29/081929
- https://smijake3.hatenablog.com/entry/2018/11/03/100133
- https://github.com/atcoder/ac-library/blob/0dd2c18e8bfc41f5f7a4a985b78c47aae945e9aa/atcoder/lazysegtree.hpp
TODO
- https://www.hamayanhamayan.com/entry/2017/07/08/173120
- https://ei1333.hateblo.jp/entry/2017/12/14/000000
- https://elliptic-shiho.github.io/segtree/segtree.pdf
- https://elliptic-shiho.hatenablog.com/entry/2024/02/14/033532
- 動的構築セグメント木
- https://scrapbox.io/data-structures/Dynamic_Segment_Tree
- http://kazuma8128.hatenablog.com/entry/2018/11/29/093827
- https://lorent-kyopro.hatenablog.com/entry/2021/03/12/025644
- http://degwer.hatenablog.com/entry/20131211/1386757368
https://lumakernel.github.io/ecasdqina/data-structure/SegmentTree/DynamicSegmentTree
- https://mugen1337.github.io/procon/DataStructure/BinaryTrieMonoid.cpp
- https://sotanishy.github.io/cp-library-cpp/data-structure/segtree/dynamic_segment_tree.cpp
- https://sotanishy.github.io/cp-library-cpp/data-structure/segtree/dynamic_lazy_segment_tree.cpp
- https://www.hamayanhamayan.com/entry/2019/02/09/103140
- https://twitter.com/noshi91/status/1338881669525172224
- 2次元セグメント木
- https://www.hamayanhamayan.com/entry/2017/12/09/015937
- https://ei1333.github.io/algorithm/segment-tree.html
- https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
- https://codeforces.com/blog/entry/74181?#comment-583268
- https://drive.google.com/file/d/1bSjYiA-nSsHzBbCnLq1GeTpRzs2Ucm0q
- https://github.com/ei1333/library/blob/master/structure/segment-tree-2d-2.cpp
https://lumakernel.github.io/ecasdqina/data-structure/SegmentTree/SegmentTree2D
- https://github.com/primenumber/ProconLib/blob/master/Structure/SegmentTree2D.cpp
- https://algoogle.hadrori.jp/algorithm/2d-segment-tree.html
- https://judge.yosupo.jp/problem/point_add_rectangle_sum
- 問題例 “RangeMinimumQuery”
- 問題例 “Longest Array Deconstruction”
- https://twitter.com/PCTprobability/status/1444372565435170816
- 問題例 “School of Killifish”
- 問題例 “Snuke Panic (2D)”
- フラクショナルカスケーディング (fractional cascading)
- https://en.wikipedia.org/wiki/Fractional_cascading
- http://sntea.hatenablog.com/entry/2017/09/28/003418
- https://www.slideshare.net/okuraofvegetable/ss-65377588
- https://www.slideshare.net/satashun/2013-25814388
- https://qiita.com/nariaki3551/items/3c5e59b3ece31a4dfce8
https://lumakernel.github.io/ecasdqina/data-structure/SegmentTree/FractionalCascadingSegmentTree
- range tree
- https://en.wikipedia.org/wiki/Range_tree
- https://kopricky.github.io/code/SegmentTrees/rangetree_pointupdate.html
- https://mugen1337.github.io/procon/DataStructure/RangeTree.cpp
- https://sotanishy.github.io/cp-library-cpp/data-structure/range_tree.cpp
- 問題例「三角形の質問」
- 四分木 (quadtree)
- https://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8
- https://sotanishy.github.io/cp-library-cpp/data-structure/quadtree.cpp
- 永続セグメント木
- https://scrapbox.io/data-structures/Persistent_Segment_Tree
- https://scrapbox.io/data-structures/Persistent_Lazy_Segment_Tree
- http://sigma425.hatenablog.com/entry/2014/12/30/164148
- https://ei1333.github.io/algorithm/segment-tree.html
- https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
- https://github.com/beet-aizu/library/blob/master/segtree/persistent/ushi.cpp
https://lumakernel.github.io/ecasdqina/data-structure/SegmentTree/PersistentSegmentTree
https://lumakernel.github.io/ecasdqina/data-structure/SegmentTree/PersistentLazySegmentTree
- https://github.com/primenumber/ProconLib/blob/master/Structure/SegmentTreePersistent.cpp
- http://monyone.github.io/teihen_library/#PersistentDynamicSumSegmentTree
- https://sotanishy.github.io/cp-library-cpp/data-structure/segtree/persistent_segment_tree.cpp
- segment tree Beats
- https://rsm9.hatenablog.com/entry/2021/02/01/220408
- https://twitter.com/fuppy_kyopro/status/1356599033439997952
- https://codeforces.com/blog/entry/57319
- https://hackmd.io/@a4YdmMWJSTa0aHKUX3wNcA/S1MJhbSLV
- https://smijake3.hatenablog.com/entry/2019/04/28/021457
- https://smijake3.hatenablog.com/entry/2019/05/18/145531
- https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
- https://kmyk.github.io/competitive-programming-library/library/data_structure/segment_tree_beats.hpp.html
- https://github.com/tjkendev/segment-tree-beats
- https://tjkendev.github.io/procon-library/cpp/range_query/segment_tree_beats_1.html
- https://mugen1337.github.io/procon/SegmentTree/SegmentTreeBeats.cpp
- https://sotanishy.github.io/cp-library-cpp/data-structure/segtree/segment_tree_beats.cpp
- https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum
- 問題例「惑星ヤナイヅの資源」
- 問題例 “I like Query Problem”
- 双対セグメント木
https://kimiyuki.net/blog/2019/02/22/dual-segment-tree/
- https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
- https://sotanishy.github.io/cp-library-cpp/data-structure/segtree/dual_segment_tree.cpp
- https://judge.yosupo.jp/problem/range_affine_point_get
- https://judge.yosupo.jp/problem/rectangle_add_point_get
- 区間等差数列加算クエリ / 区間等差数列更新クエリ
- https://null-mn.hatenablog.com/entry/2021/08/22/064325
- https://twitter.com/yosupot/status/1104175527923986432
- https://twitter.com/kuma_program/status/1358762477589155840
- https://judge.yosupo.jp/problem/range_linear_add_range_min
- $A_{l \oplus x} A_{(l + 1) \oplus x} \cdots A_{(r - 1) \oplus x}$
- 定数時間アルゴリズム
- https://docs.google.com/presentation/d/1AvECxRv7hLbCNdXjERzhuJuYcV5fYFPpLA_S4QppbRI
- 円環版
get
- https://twitter.com/risujiroh/status/1654163763971358723
Submissons
Verified with
Code
Back to top page