永続配列
(DataStructure/misc/PersistentArray.py)

• View this file on GitHub
• Last update: 2021-07-18 20:19:20+09:00

概要

永続化された配列。つまり、代入操作前と後のバージョンを常に保持し、全バージョンに対するアクセスと更新が可能な配列。

使い方

init_persistent_array(array: Sequence[Any]) -> PersistentArray
長さ $n$ の配列 array の永続配列を返す。計算量 $O(n \log n)$

永続配列のメソッド set と get によって、全バージョンに対するアクセスと更新が可能。

• set(i: int, val: Any) -> PersistentArray
  $i$ 番目の要素に val を代入した永続配列を返す。計算量 $O(\log n)$

• get(i: int) -> Any
  $i$ 番目の要素を返す。計算量 $O(\log n)$

Required by

• 永続 Union Find (DataStructure/UnionFind/PersistentUnionFind.py)

Verified with

• TestCase/unittest/PersistentArray.unittest.test.py

Code

class PersistentArray:
    LOG = 4
    MASK = (1 << LOG) - 1

    def __init__(self,):
        self.val = None
        self.ch = [None] * (1 << self.LOG)

    def set(self, i, val):
        pa = PersistentArray()
        pa.val = self.val
        pa.ch = self.ch[:]
        if i == 0:
            pa.val = val
        else:
            pa.ch[i & self.MASK] = pa.ch[i & self.MASK].set(i >> self.LOG, val)
        return pa

    def get(self, i):
        pa = self
        while i != 0:
            pa = pa.ch[i & self.MASK]
            i = i >> self.LOG
        return pa.val


def init_persistent_array(array):
    LOG = 4
    MASK = (1 << LOG) - 1

    def init_set(i, val, pa):
        if pa is None:
            pa = PersistentArray()
        if i == 0:
            pa.val = val
        else:
            pa.ch[i & MASK] = init_set(i >> LOG, val, pa.ch[i & MASK])
        return pa

    pa = None
    for i, val in enumerate(array):
        pa = init_set(i, val, pa)
    return pa

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page