lib.data_structure package
Submodules
lib.data_structure.lazy_segment_tree module
- class lib.data_structure.lazy_segment_tree.LazySegmentTree(n: int, id_t: Callable[[], T], id_f: Callable[[], F], op: Callable[[T, T], T], mapping: Callable[[T, F], T], composition: Callable[[F, F], F], aggregation: Callable[[F, int], F])
ベースクラス:
Generic[T,F]遅延セグメント木
- apply(left: int, right: int, val: F, begin: int = 0, end: int | None = None, idx: int = 1)
区間 [l, r) に作用を適用する
- パラメータ:
left (int) -- 区間の左端
right (int) -- 区間の右端
val (F) -- 作用
- classmethod from_array(array: list[T], id_t: Callable[[], T], id_f: Callable[[], F], op: Callable[[T, T], T], mapping: Callable[[T, F], T], composition: Callable[[F, F], F], aggregation: Callable[[F, int], F]) LazySegmentTree[T, F]
配列から遅延セグメント木を構築する
- パラメータ:
array (list[T]) -- 配列
id_t (Callable[[], T]) -- 値の単位元
id_f (Callable[[], F]) -- 作用の単位元
op (Callable[[T, T], T]) -- 二項演算
mapping (Callable[[T, F], T]) -- 作用の適用
composition (Callable[[F, F], F]) -- 作用の合成
aggregation (Callable[[F, int], F]) -- 作用の繰り返し
- 戻り値:
構築したセグメント木
- 戻り値の型:
LazySegmentTree[T, F]
- get_range(left: int, right: int, begin: int = 0, end: int | None = None, idx: int = 1)
区間 [l, r) の値を取得する
- パラメータ:
left (int) -- 区間の左端
right (int) -- 区間の右端
lib.data_structure.segment_tree module
- class lib.data_structure.segment_tree.SegmentTree(n: int, id_: Callable[[], T], op: Callable[[T, T], T])
ベースクラス:
Generic[T]セグメント木
- classmethod from_array(array: list[T], id_: Callable[[], T], op: Callable[[T, T], T]) SegmentTree[T]
配列からセグメント木を構築する
- パラメータ:
array (list[T]) -- 配列
id (Callable[[], T]) -- 単位元を返す関数
_op (Callable[[T, T], T]) -- 二項演算を行う関数
- 戻り値:
構築したセグメント木
- 戻り値の型:
SegmentTree[T]
- get_range(l: int, r: int) T
区間 [l,r) の演算結果を返す
- パラメータ:
l (int) -- 区間の左端
r (int) -- 区間の右端
- 戻り値:
演算結果
- 戻り値の型:
T
- update(i: int, x: T) None
i 番目の要素を x に更新する
- パラメータ:
i (int) -- 更新する要素のインデックス
x (T) -- 更新する値
lib.data_structure.union_find module
- class lib.data_structure.union_find.UnionFind(n: int)
ベースクラス:
object- find(u: int) int
要素 u が属するグループの根を返す
- パラメータ:
u (int) -- 要素の番号
- 戻り値:
要素 u が属するグループの根
- 戻り値の型:
int
- group_count() int
グループの個数を返す
- 戻り値:
グループの個数
- 戻り値の型:
int
- is_same(u: int, v: int) bool
要素 u と要素 v が同じグループに属するかを返す
- パラメータ:
u (int) -- 要素の番号
v (int) -- 要素の番号
- 戻り値:
要素 u と要素 v が同じグループに属するか
- 戻り値の型:
bool
- size(u: int) int
要素 u が属するグループの頂点数を返す
- パラメータ:
u (int) -- 要素の番号
- 戻り値:
要素 u が属するグループの頂点数
- 戻り値の型:
int
- unite(u: int, v: int) bool
要素 u が属するグループと要素 v が属するグループを併合する
- パラメータ:
u (int) -- 要素の番号
v (int) -- 要素の番号
- 戻り値:
併合が行われたか
- 戻り値の型:
bool
lib.data_structure.weighted_union_find module
- class lib.data_structure.weighted_union_find.WeightedUnionFind(n: int, op: Callable[[T, T], T], identity_func: Callable[[], T], inverse: Callable[[T], T])
ベースクラス:
Generic[T]重み付きUnion-Find (ポテンシャル付きUnion-Find)
2つの要素 x, y を、重みの差が w (weight(y) - weight(x) = w) となるように 併合することができるデータ構造。アーベル群をなす演算であれば、どのような 型の重みでも扱うことが可能。
- diff(x: int, y: int) T | None
要素 x と y の重みの差 (weight(y) - weight(x)) を計算する。
- find(x: int) int
要素 x の根を求め、経路圧縮を行う。
注釈
この実装は再帰を使用しているため、要素数が多い場合は Pythonの再帰深度上限に達する可能性がある。
- get_weight(x: int) T
要素 x のポテンシャル（根からの重み）を返す。
- group_count() int
連結成分の数を返す。
- is_same(x: int, y: int) bool
要素 x と y が同じ集合に属するか判定する。
- size(x: int) int
要素 x が属する集合の要素数を返す。
- unite(x: int, y: int, w: T) bool
要素 x と y を、weight(y) - weight(x) = w となるように併合する。