n_ha_ac_library package

Submodules

n_ha_ac_library.cum module

累積和

class n_ha_ac_library.cum.Cum(v: int | list[T], op: Callable[[T, T], T], inv: Callable[[T], T], e: T)

ベースクラス: Generic

累積和

Tip

型が任意なのでデフォルト値はありません。整数のみを扱う場合は CumInt を利用できます。

Tip

T: 群 ( get で left が常に 0 ならば左単位的マグマ)

build(a: list[T]) → None

構築

リスト a を用いて累積和のリスト self.data を構築します。 要素数で初期化をした場合に、一度のみ実行可能です。

パラメータ:: a (list[T]) -- リスト

get(left: int, right: int | None = None) → T

二項演算を作用させた値の取得

半開区間[left, right)の要素に二項演算を作用させた値を求めます。

パラメータ:

left (int) -- 左端
right (int | None, optional) -- 右端. Defaults to None.

戻り値:

累積和

戻り値の型:

T

set(index: int, value: T) → None

値の更新

index の要素の値を value に更新します。

パラメータ:

index (int) -- インデックス
value (T) -- 更新値

class n_ha_ac_library.cum.CumInt(v: int | list[int], op: ~typing.Callable[[int, int], int] = <function _op>, inv: ~typing.Callable[[int], int] = <function _inv>, e: int = 0)

ベースクラス: Cum[int]

整数用累積和

Cum[int] を継承した整数のみに対応した累積和です。デフォルト値を用いた場合は一般的な累積和を求めます。

サンプル

>>> A = [3, 1, 4]
>>> cum = CumInt(A) # 累積和の構築
>>> len(cum) # 要素数
3
>>> cum[1] # A[1]の値
1
>>> cum[0:3] # A[0] + A[1] + A[2]の値
8
>>> cum[0] = 1 # A[0]の値を1に更新
>>> cum[0:3] # A[0] + A[1] + A[2]の値
6

Module contents

N-ha's AtCoder library