CPLib.LDSegtree
Defined in cp-library@0.15.2
モノイド構造および作用が動的に決められる遅延伝搬セグメント木
コンストラクタでモノイドおよび作用を指定する点以外は、CPLib.LSegtreeと同じです。
モノイド構造・作用が静的に決まる場合はCPLib.LSegtreeの方が高速です。
制約・計算量の n は要素数です。計算量はop, act_op, actがO(1)で動くとしたものです。
制約:作用は次を満たす(a, bは作用、x, yは値)
- act(act_unit, x) = x
- act(a, op(x, y)) = op(act(a, x), act(a, y))
- act(act_op(a, b), x) = act(b, act(a, x))
Examples
// 区間への加算と、区間の最大値の取得ができるセグメント木
let tree = build(
[1, 2, 3],
minimum, |(x, y)| max(x, y), // 値モノイド:最大値
0, |(a, b)| a + b, // 作用モノイド:加法
|(a, x)| x + a // 作用:加算
);
let tree = tree.act_range(0, 2, 10); // [11, 12, 3]
assert_eq(|_|"", tree.fold(1, 3), 12)
Values
namespace CPLib.LDSegtree
@
Type: Std::I64 -> CPLib.LDSegtree::LDSegtree m a -> m
セグメント木の要素を取得する
制約:0 <= i < n
計算量:O(log n)
Parameters
i: インデックス(0-indexed)tree: セグメント木
@size
Type: CPLib.LDSegtree::LDSegtree m a -> Std::I64
セグメント木の要素数を取得する
計算量:O(1)
Parameters
tree: セグメント木
act_at
Type: Std::I64 -> a -> CPLib.LDSegtree::LDSegtree m a -> CPLib.LDSegtree::LDSegtree m a
1つの要素に作用を適用する
act_range(i, i + 1, a)と同じ結果になる。
制約:0 <= i < n
計算量:O(log n)
Parameters
i: インデックス(0-indexed)a: 作用tree: セグメント木
act_range
Type: Std::I64 -> Std::I64 -> a -> CPLib.LDSegtree::LDSegtree m a -> CPLib.LDSegtree::LDSegtree m a
半開区間[l, r)に右から作用を適用する
制約:0 <= l <= r <= n
計算量:O(log n)
Parameters
l: 区間の左端 (0-indexed)r: 区間の右端 (0-indexed, exclusive)a: 適用する作用tree: セグメント木
build
Type: Std::Array m -> m -> ((m, m) -> m) -> a -> ((a, a) -> a) -> ((a, m) -> m) -> CPLib.LDSegtree::LDSegtree m a
要素の配列からセグメント木を作成する
計算量:O(n)
Parameters
elems: セグメント木の要素を格納する配列unit: 値モノイドの単位元op: 値モノイドの演算子act_unit: 作用モノイドの単位元act_op: 作用モノイドの演算子act: 右作用
calc_max_right
Type: Std::I64 -> (m -> Std::Bool) -> CPLib.LDSegtree::LDSegtree m a -> Std::I64
f(fold(l, r))が真になる最大のrを、木の上の二分探索で求める
制約:0 <= l <= n、f(unit)が真、fは単調(区間を右に伸ばして偽になったら、さらに伸ばしても真にならない)
計算量:O(log n)。fの呼び出しもO(log n)回。
Parameters
l: 区間の左端 (0-indexed)f: 区間の畳み込みについての条件tree: セグメント木
Examples
// 区間への加算と、区間の最大値の取得ができるセグメント木
let tree = build([1, 2, 5, 4], minimum, |(x, y)| max(x, y), 0, |(a, b)| a + b, |(a, x)| x + a);
let tree = tree.act_range(0, 2, 2); // [3, 4, 5, 4]
// 区間[0, 2)の最大値は4、区間[0, 3)の最大値は5
assert_eq(|_|"", tree.calc_max_right(0, |x| x <= 4), 2)
calc_min_left
Type: Std::I64 -> (m -> Std::Bool) -> CPLib.LDSegtree::LDSegtree m a -> Std::I64
f(fold(l, r))が真になる最小のlを、木の上の二分探索で求める
制約:0 <= r <= n、f(unit)が真、fは単調(区間を左に伸ばして偽になったら、さらに伸ばしても真にならない)
計算量:O(log n)。fの呼び出しもO(log n)回。
Parameters
r: 区間の右端 (0-indexed, exclusive)f: 区間の畳み込みについての条件tree: セグメント木
Examples
// 区間への加算と、区間の最大値の取得ができるセグメント木
let tree = build([1, 2, 5, 4], minimum, |(x, y)| max(x, y), 0, |(a, b)| a + b, |(a, x)| x + a);
let tree = tree.act_range(0, 2, 2); // [3, 4, 5, 4]
// 区間[3, 4)の最大値は4、区間[2, 4)の最大値は5
assert_eq(|_|"", tree.calc_min_left(4, |x| x <= 4), 3)
create
Type: Std::I64 -> m -> ((m, m) -> m) -> a -> ((a, a) -> a) -> ((a, m) -> m) -> CPLib.LDSegtree::LDSegtree m a
すべての要素が単位元であるような遅延伝搬セグメント木を作成する
計算量:O(n)
Parameters
n: セグメント木の要素数unit: 値モノイドの単位元op: 値モノイドの演算子act_unit: 作用モノイドの単位元act_op: 作用モノイドの演算子act: 右作用
fold
Type: Std::I64 -> Std::I64 -> CPLib.LDSegtree::LDSegtree m a -> m
半開区間[l, r)にある要素の畳み込みを計算する
制約:0 <= l <= r <= n
計算量:O(log n)
Parameters
l: 区間の左端 (0-indexed)r: 区間の右端 (0-indexed, exclusive)tree: セグメント木
fold_all
Type: CPLib.LDSegtree::LDSegtree m a -> m
すべての要素の畳み込みを計算する
計算量:O(log n)
Parameters
tree: セグメント木
init
Deprecated: Use CPLib.LDSegtree::create instead, and swap the two arguments of the action function: init takes it as (m, a) -> m, with the value first, while create takes it as (a, m) -> m, with the action first.
Type: Std::I64 -> m -> ((m, m) -> m) -> a -> ((a, a) -> a) -> ((m, a) -> m) -> CPLib.LDSegtree::LDSegtree m a
createの別名(非推奨)。ただし作用actは、値を先に取る(m, a) -> mで受け取る
set
Type: Std::I64 -> m -> CPLib.LDSegtree::LDSegtree m a -> CPLib.LDSegtree::LDSegtree m a
セグメント木の要素を設定する
制約:0 <= i < n
計算量:O(log n)
Parameters
i: インデックス(0-indexed)value: 設定する値tree: セグメント木
Types and aliases
namespace CPLib.LDSegtree
LDSegtree
Defined as: type LDSegtree m a = unbox struct { ...fields... }
遅延伝搬セグメント木の型。
パラメータmは「値」となるモノイドの型、aは「右作用」するモノイドの型。