Nim-ACL

Persistent Segment Tree（永続セグメント木）

1個の木がすべてのノードを管理し、PersistentVersionが各時点の 根を表します。

数列をコピーするときは要素を複製せず、versionを代入します。

versions[x] = versions[y]

初期化

一般形は次のとおりです。

type Tree =
  PersistentSegTreeType[S](
    op,
    e,
  )

var tree =
  Tree.init(
    valuesOrLength,
    expectedUpdates = 0,
  )

opとeの加算モノイドの具体例は次のとおりです。

proc op(
    left,
    right: int,
): int =
  left + right

proc e(): int =
  0

このop, eを一般形へ渡します。

type SumTree =
  PersistentSegTreeType[int](
    op,
    e,
  )

var tree =
  SumTree.init(
    n,
    expectedUpdates = q,
  )

長さだけを渡すと、すべての要素をe()で初期化します。

簡略constructorも使用できます。

var tree =
  initPersistentSegmentTree(
    n,
    op,
    e,
    expectedUpdates = q,
  )

初期version

let version =
  tree.initialVersion

versionは軽量なroot番号です。

一点更新

一般形は次のとおりです。

newVersion =
  tree.set(
    version,
    position,
    value,
  )

元のversionは変更されません。

versions[x] =
  tree.set(
    versions[x],
    y,
    z,
  )

短縮記法では、渡したversion変数を新しいversionへ更新します。

tree[version][position] = value

または、

tree[version, position] = value

一点取得

一般形は次のとおりです。

value =
  tree.get(
    version,
    position,
  )

短縮記法は次のとおりです。

value = tree[version][position]

または、

value = tree[version, position]

区間積

一般形は次のとおりです。

answer =
  tree.prod(
    version,
    range,
  )

半開区間の端点を直接渡すこともできます。

answer =
  tree.prod(
    version,
    left,
    right,
  )

短縮記法は次のとおりです。

answer = tree[version][left ..< right]

または、

answer = tree[version, left ..< right]

全体積

answer =
  tree.allProd(
    version
  )

配列への復元

values =
  tree.toSeq(
    version
  )

計算量はO(n log n)です。主にdebug用途です。

version view

tree[version]はtreeとversionを参照する一時的なviewです。

tree[version][position] = value
answer = tree[version][range]

viewを変数へ保存することもできますが、元のtreeとversionより長く 保持しないでください。

expectedUpdates

raw static tuple形式

PersistentSegTree[S, (op: ..., e: ...)]は低水準APIです。

同じsignatureを持つ複数の匿名procをraw static tupleへ直接渡すと、 Nimが後のprocにも最初のprocを再利用する場合があります。

通常はPersistentSegTreeTypeまたは initPersistentSegmentTreeを使用してください。

計算量