永続Binary Indexed Tree
(DataStructure/BinaryIndexedTree/PersistentBinaryIndexedTree.py)

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

概要

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

使い方

PersistentBinaryIndexedTree(n: int, root=None)
長さ $n$ の Persistent Binary Indexed Tree を構築する。計算量 $O(1)$

• build(array: Sequence[int]) -> None
  Persistent Binary Indexed Tree を array で初期化する。add や sum を実行出す前に、必ず build しておくこと。たとえ全ての要素が $0$ である場合も、[0] * n を与えて build しておくこと。計算量 $O(n)$

• add(i: int, val: int) -> PersistentBinaryIndexedTree
  $i$ 番目の要素に val を加えた Persistent Binry Indexed Tree を返す。計算量 $O(\log n)$

• sum(l: int, r: int) -> int
  $\lbrack l, r)$ 番目の要素の総和を返す。計算量 $O(\log n)$

Code

class PersistentBinaryIndexedTree:
    def __init__(self, n, root=None):
        self.root = root
        self.n = n
        self.size = 1 << n.bit_length()

    def build(self, array):
        n = len(array)
        bit = [[None, None, array[i - 1] if 0 <= i - 1 < n else 0] for i in range(self.size)]
        for i in range(1, self.size):
            if i + (i & -i) < self.size:
                bit[i + (i & -i)][2] += bit[i][2]
        bit[0] = tuple(bit[0])
        for k in range(self.size.bit_length() - 1):
            for i in range(1 << k, self.size, 1 << (k + 1)):
                if k == 0:
                    bit[i] = tuple(bit[i])
                else:
                    l, r = i - (1 << (k - 1)), i + (1 << (k - 1))
                    bit[i][0], bit[i][1] = bit[l], bit[r]
                    bit[i] = tuple(bit[i])
        self.root = bit[self.size >> 1]

    def _sum(self, i):
        s = 0
        nd = self.root
        idx = self.size >> 1
        for h in reversed(range(self.size.bit_length() - 2)):
            if i < idx:
                nd = nd[0]
                idx -= 1 << h
            else:
                s += nd[2]
                nd = nd[1]
                idx += 1 << h
        if i >= idx:
            s += nd[2]
        return s

    def _add_rec(self, i, idx, diff, val, nd):
        if i == idx:
            return (nd[0], nd[1], nd[2] + val)
        elif i < idx:
            ndl = self._add_rec(i, idx - diff, diff >> 1, val, nd[0])
            if idx - (idx & (-idx)) < i:
                return (ndl, nd[1], nd[2] + val)
            return (ndl, nd[1], nd[2])
        else:
            ndr = self._add_rec(i, idx + diff, diff >> 1, val, nd[1])
            return (nd[0], ndr, nd[2])

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

    def add(self, i, val):
        i += 1
        idx = self.size >> 1
        root = self._add_rec(i, idx, idx >> 1, val, self.root)
        return PersistentBinaryIndexedTree(self.n, root)

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