Nim-ACL

Monoid SegTree facade

概要

monoid_segtreeは、Monoid記述子からSegTreeとLazySegTreeを 構築するための公開facadeです。

既存のcallback constructorやcore moduleは変更しません。 新しい記述子形式を追加するため、従来のコードもそのまま利用できます。

import

import atcoder/extra/structure/monoid_segtree

このimportから次をまとめて利用できます。

chaemon_headerをincludeしたコードからも利用できます。

Monoid記述子

proc add(a, b: int): int =
  a + b

proc zero(): int =
  0

useMonoid(
  SumMonoid,
  int,
  add,
  zero,
)

SegTreeの構築

初期配列から構築できます。

var tree = initSegTree(
  SumMonoid,
  @[1, 2, 3, 4],
)

UFCS形式も利用できます。

var tree = SumMonoid.initSegTree(
  @[1, 2, 3, 4],
)

長さから構築すると、各葉はdefault(S)ではなく Monoidの単位元で初期化されます。

var tree = SumMonoid.initSegTree(8)

単位元が0ではないMonoidでも正しく動作します。

proc minOp(a, b: int): int =
  min(a, b)

proc minIdentity(): int =
  high(int)

useMonoid(
  MinMonoid,
  int,
  minOp,
  minIdentity,
)

var minimums = MinMonoid.initSegTree(8)

doAssert minimums.prod(0..<8) == high(int)

ActionMonoid

作用を表す公開形式では、作用Monoid Fを値Monoid Sより 先に記述します。

useActionMonoid(
  Name,
  FMonoid,
  SMonoid,
  mapping,
)

これは数学的な「FがSへ作用する」という読み順です。

従来形式も互換APIとして維持します。

useActedMonoid(
  Name,
  SMonoid,
  FMonoid,
  mapping,
)

内部実装の型順序は変更されません。

LazySegTreeの構築

useActionMonoid(
  RangeAddMax,
  AddMonoid,
  MaxMonoid,
  mappingAdd,
)

var tree = RangeAddMax.initLazySegTree(
  @[1, 2, 3, 4],
)

記述子を先頭に置く形式も利用できます。

var tree = initLazySegTree(
  RangeAddMax,
  @[1, 2, 3, 4],
)

長さconstructorは値Monoidの単位元で初期化します。

var tree = RangeAddMax.initLazySegTree(8)

作用の合成順序

作用Monoidの演算op(f, g)は、gを適用した後にfを適用する 合成を表します。

op(f, g)(x) = f(g(x))

affine変換では次の形です。

proc compose(f, g: Affine): Affine =
  (
    a: f.a * g.a,
    b: f.a * g.b + f.b,
  )

この順序は非可換なaffine作用を用いたtestで固定されています。

区間操作

構築後の操作は既存のSegTree APIと同じです。

tree.set(position, value)
tree.get(position)
tree.prod(0..<n)
tree.apply(1..<4, action)

RangeTypeによる区間指定も利用できます。

既存callback APIとの共存

既存のcallback constructorは変更されません。

var tree = segtree.initSegTree[int](
  values,
  op,
  identity,
)

LazySegTreeのcallback constructorも維持されます。 facadeは記述子を既存callback形式へ変換する薄い層です。

境界条件

計算量

facadeは既存実装へ委譲するため、計算量は変わりません。

操作 計算量
構築 O(n)
set O(log n)
get 既存core契約
prod O(log n)
LazySegTreeのapply O(log n)

検証

恒久testで次を確認しています。