永続セグメント木
(DataStructure/SegmentTree/PersistentSegmentTree.py)

• View this file on GitHub
• Last update: 2021-02-14 13:08:01+09:00

概要

Segment Tree を永続化したデータ構造。定数倍が重い。

使い方

PersistentSegmentTree(n: int, op: Callable[[T, T], T], e: T, root=None)
長さ $n$ の Persistent Segment Tree を構築する。計算量 $O(1)$

• build(array: Sequence[Any]) -> None
  Persistent Segment Tree を array で初期化する。計算量 $O(n)$

• __getitem__(i: int) -> T
  $i$ 番目の要素を返す。計算量 $O(1)$

• update(i: int, val: T) -> PersistentSegmentTree
  $i$ 番目の要素を val に更新した Persistent Segment Tree を返す。計算量 $O(\log n)$

• all_fold() -> T
  $[0, n)$ 番目の要素の畳み込み結果を返す。計算量 $O(1)$

• fold(l: int, r: int) -> T
  $[l, r)$ 番目の要素の畳み込み結果を返す。計算量 $O(\log n)$

Code

class PersistentSegmentTree:
    def __init__(self, n, op, e, root=None):
        self.op = op
        self.e = e
        self.root = root
        self.n = n
        self.log = (n - 1).bit_length()
        self.size = 2 ** self.log

    def build(self, array):
        array = [(None, None, array[i] if i < self.n else self.e) for i in range(self.size)]
        for h in range(self.log):
            tmp = []
            for i in range(1 << (self.log - h - 1)):
                nd = self.make_parent(array[i << 1 | 0], array[i << 1 | 1])
                tmp.append(nd)
            array, tmp = tmp, array
        self.root = array[0]

    def __getitem__(self, i):
        nd = self.root
        for h in range(self.log):
            if (i >> (self.log - h - 1)) & 1:
                nd = nd[1]
            else:
                nd = nd[0]
        return nd[2]

    def update(self, i, val):
        nd = self.root
        stack = [nd]
        for h in range(self.log):
            if (i >> (self.log - h - 1)) & 1:
                nd = nd[1]
            else:
                nd = nd[0]
            stack.append(nd)
        nd = (None, None, val)
        for ndc, ndp in zip(stack[::-1], stack[::-1][1:]):
            if ndp[0] is ndc:
                nd = self.make_parent(nd, ndp[1])
            else:
                nd = self.make_parent(ndp[0], nd)
        return PersistentSegmentTree(self.size, self.op, self.e, nd)

    def make_parent(self, ndl, ndr):
        return (ndl, ndr, self.op(ndl[2], ndr[2]))

    def all_fold(self):
        return self.root[2]

    def fold(self, l, r):
        return self._fold(l, r, 0, self.n, self.root)

    def _fold(self, a, b, l, r, nd):
        if r <= a or b <= l:
            return self.e
        if a <= l and r <= b:
            return nd[2]
        vl = self._fold(a, b, l, (l + r) >> 1, nd[0])
        vr = self._fold(a, b, (l + r) >> 1, r, nd[1])
        return self.op(vl, vr)

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