区間更新 + 一点取得 セグメント木 (Dual Segment Tree)
(src/data-structure/segment-tree/range-mapping-point-fold-segment-tree.hpp)
Appendix
Segment Tree の細かい仕様について
コンストラクタ
RangeMappingPointFoldSegmentTree
のエイリアスとして DualSegmentTree
を提供している。
(1) DualSegmentTree< O >(usize n)
(2) DualSegmentTree< O >(usize n, OT v)
(3) DualSegmentTree< O >(std::vector< OT > vs)
- 列 $a$ を長さ $n$ の列で初期化する。各要素の初期値は
V::identity()
となる。
- 列 $a$ を長さ $n$ の列で初期化する。各要素の初期値は
v
となる。
- 列 $a$ を
vs
で初期化する。
制約
計算量
build
void build(vector< OT > vs)
列 $(a_0, a_1, \dots, a_{n-1})$ を vs
で初期化して再構築する。
制約
計算量
size
扱っている列 $(a_0, a_1, \dots, a_{n - 1})$ の長さ $n$ を返す。
計算量
set
$a_i \leftarrow x$ で更新する。
制約
計算量
apply
(1) void apply(usize i, OT x)
(2) void apply(usize l, usize r, OT x)
- $a_i \leftarrow f(a_i)$ で更新する。
- 任意の $l \leq i < r$ について $a_i \leftarrow f(a_i)$ で更新する。
制約
- $0 \leq i < n$
- $0 \leq l \leq r \leq n$
計算量
fold
$a_i$ を返す。
制約
計算量
Depends on
Required by
Verified with
Code
Back to top page